Physical gels with remarkable properties were obtained by copolymerization of acrylamide with the hydrophobic monomer stearyl methacrylate (C18) in a micellar solution of cetyltrimethylammonium bromide (CTAB) containing up to 15 mol% sodium dodecyl sulfate (SDS). The addition of SDS causes the CTAB micelles to grow and thus enables solubilization of C18. The gels exhibit time-dependent dynamic moduli, high elongation ratios at break (1800-5000%), and self-healing, as evidenced by rheological and mechanical measurements and substantiated by dynamic light scattering. As the size of the micelles in the gelation solution increases, both the degree of temporary spatial inhomogeneity and the lifetime of hydrophobic associations in the gels increase while the elongation ratio at break decreases. Although the physical gels were insoluble in water due to strong hydrophobic interactions, they could be solubilized in surfactant solutions thus providing a means of characterization of the network chains. Viscometric and rheological behaviors of polymer solutions show a substantial increase in the associativity of the network chains with rising micelle size, which results in prolonged lifetime of hydrophobic associations acting as physical cross-links in gels. The internal dynamics of self-healing gels could thus be controlled by the associativity of the network chains which in turn depends on the size of CTAB micelles.