We report the effect of native cyclodextrins (α, β, and γ) and selected derivatives in modulating the self-assembly of the nonionic surfactant polyoxyethylene cholesteryl ether (ChEO10) and its mixtures with triethylene glycol monododecyl ether (C12EO3), which form wormlike micelles. Cyclodextrins (CDs) generally induce micellar breakup through a host-guest interaction with surfactants; instead, we show that a constructive effect, leading to gel formation, is obtained with specific CDs and that the widely invoked host-guest interaction may not be the only key to the association. When added to wormlike micelles of ChEO10 and C12EO3, native β-CD, 2-hydroxyethyl-β-CD (HEBCD), and a sulfated sodium salt of β-CD (SULFBCD) induce a substantial increase of the viscoelasticity, while methylated CDs rupture the micelles, leading to a loss of the viscosity, and the other CDs studied (native α- and γ- and hydroxypropylated CDs) show a weak interaction. Most remarkably, the addition of HEBCD or SULFBCD to pure ChEO10 solutions (which are low-viscosity, Newtonian fluids of small, ellipsoidal micelles) induces the formation of transparent gels. The combination of small-angle neutron scattering, dynamic light scattering, and cryo-TEM reveals that both CDs drive the elongation of ChEO10 aggregates into an entangled network of wormlike micelles. (1)H NMR and fluorescence spectroscopy demonstrate the formation of inclusion complexes between ChEO10 and methylated CDs, consistent with the demicellization observed. Instead, HEBCD forms a weak complex with ChEO10, while no complex is detected with SULFBCD. This shows that inclusion complex formation is not the determinant event leading to micellar growth. HEBCD:ChEO10 complex, which coexists with the aggregated surfactant, could act as a cosurfactant with a different headgroup area. For SULFBCD, intermolecular interactions via the external surface of the CD may be more relevant.