The microstructure and dynamics of self-assembled wormlike micellar solutions (WLMs) lead to rheological characteristics similar to polymer solutions, including network formation, shear alignment, and non-linear instabilities such as shear banding. Here, we show enhancement of the rheological properties of WLMs by introduction of nanoparticles smaller than the mesh size (a = 30 nm) of the micellar network. Such micelle-nanoparticle mixtures exhibit large increases in viscosity as well as suppressed shear banding over a wide range of surfactant concentration. Combining rheology, flow-birefringence, light and neutron scattering and cryo-electron microscopy provides a microstructural understanding of the effects of nanoparticle addition on the WLM network. The results indicate densification of the micellar mesh near the particles as well as hindered shear-alignment, suggesting that the particles actively participate in the micellar network due to specific micelle-particle interactions. Measurements using isothermal titration calorimetry suggest that the micelles associate with an adsorbed surfactant layer on the surface of the particles with energies of O(10kT). This association of micelles with the nanoparticles results in an increase in the effective number of network junctions, and leads to the observed hindered mobility of segments and resulting increase in viscosity of the self-assembled network.