Cationic surfactants having long (C22) mono-unsaturated tails were studied in aqueous solutions containing salt using steady and dynamic rheology. The surfactant erucyl bis(hydroxyethyl)methylammonium chloride self-assembles into giant wormlike micelles, giving rise to unusually strong viscoelasticity. Under ambient conditions, the viscosity enhancement due to surfactant exceeds a factor of 107. Some samples behave as gel-like solids at low temperatures and revert to the viscoelastic (Maxwellian) response only at higher temperatures. These samples display appreciable viscosities (> 10 Pa·s) up to very high temperatures (ca. 90°C). Salts with counterions that penetrate into the hydrophobic interior of the micelles, such as sodium salicylate, are much more efficient at promoting self-assembly than salts with nonbinding counterions, such as sodium chloride. Changing the surfactant headgroup to the more conventional trimethylammonium group reduces the viscosity at high temperatures.