Different reversible molecular interactions have been used in the past few years to generate self-healing in synthetic hydrogels. However, self-healing hydrogels synthesized so far suffer from low mechanical strength which may limit their use in any stress-bearing applications. Here, we present a simple technique to heal mechanically strong polyacrylamide hydrogels formed via hydrophobic interactions between stearyl groups. A complete healing in the hydrogels was achieved by the treatment of the damaged areas with an aqueous solution of wormlike sodium dodecyl sulfate micelles. The micelles in the healing agent solubilize the hydrophobes in the cut surfaces, so that they easily find their partners in the other cut surface due to the hydrophobic interactions. Surfactant-induced healing produces high toughness (similar to 1 MPa) gels withstanding 150 kPa of stress at a deformation ratio of 1,100 %. The healing technique developed here is generally applicable to the physical gels formed by hydrophobic associations.