We study the rheology and microstructure of self-assembled wormlike micellar solutions (WLMs) in the presence of nanoparticles smaller than the mesh size of the micelle network. The addition of cationically modified silica nanoparticles (d = 30 nm) to WLMs of cetyltrimethylammonium bromide (CTAB) significantly modifies the linear and non-linear rheology of the micellar network. Combining rheology, flow-birefringence, light and neutron scattering and cryo-electron microscopy measurements provides a microstructural basis for the effects of the nanoparticles on the WLM network. The results indicate densification of the micellar mesh near the particles, suggesting that the particles actively participate in the micellar network due to specific micelle-particle interactions. Measurements of the energetics of these interactions have been carried out using isothermal titration calorimetry, suggesting that the micelles associate with an adsorbed surfactant layer on the surface of the particle. This leads to increases in elasticity of the network as well as hindered micellar alignment under flow, resulting in macroscopic increases in viscosity and suppression of the shear banding instability for concentrated CTAB solutions. The distribution of particles in the WLM network is consistent with an effective interparticle attraction mediated by the adsorbed surfactants, which leads to phase separation at higher nanoparticle loading.