The strong associative behaviour between cholesterol-modified dextran (CMD) and short and long polyoxyethylene cholesteryl ether (ChEO10) micelles were investigated using rheology and small-angle neutron scattering (SANS). In solutions of short rod-like micelles (ChEO10 alone), the addition of 5.0 wt% CMD induced a remarkable transition from a Newtonian system to a highly solid-like viscoelastic network, with an increase in zero-shear viscosity of over 5 orders of magnitude. The frequency sweeps at ChEO10 concentrations above 2.5 wt% were fitted to a Maxwell model with 3 elements and, quite remarkably, fell onto a single master curve, while no network was formed at 2.5 wt% micelles. Viscoelastic solutions of wormlike micelles (WLMs) were obtained by adding the co-surfactant triethylene glycol monododecyl ether (C12EO3) to ChEO10 solutions at a constant ChEO10/C12EO3 ratio of 5/1. The introduction of CMD into the WLM solutions induced a transition to a more liquid-like behaviour (G″/G′ increased), however both moduli increased by one order of magnitude. At the lowest ChEO10 concentration (2.5%), the solid-like behaviour was lost. Overall, a comparable rheological response was obtained for the WLM and the short rods with CMD, however the WLM/CMD behaviour suggested a wider spectrum of relaxation processes, longer relaxation times and higher plateau moduli. SANS data from the polymer/micelles mixtures displayed a strong structural peak and were remarkably identical for both ChEO10/CMD and ChEO10/C12EO3/CMD systems, suggesting a very similar type of network structure, independently of the initial size of the micelles. Overall, all the results taken together show a very high affinity between the polymer and the micelles and suggest a breakup of the WLM induced by CMD. The resulting network is constituted by polymeric chains connected by micellar aggregates through hydrophobic interactions between the micellar cholesterol cores and the pendent cholesterol moieties of the polymer