Expanding the application of high-strength hydrogels has attracted tremendous attention in the fields of biomedical engineering, agriculture and wastewater treatment owing to their versatility and outstanding deformation resistance. In this paper, a new class of graphene oxide (GO)/hydrophobically associated polyacrylamide composite hydrogels (GHA gels) were constructed by a simple one-pot method. Without the introduction of any conventional organic cross-linkers, the GHA gels physically cross-linked by GO sheets and hydrophobically associated domains demonstrated superior mechanical strength and high toughness. Because the networks of hydrophobically associated polyacrylamide could swiftly reconstruct without any external stimuli, the GHA gels exhibited prominent self-healing ability and fatigue resistance. The GHA gels also manifested improved adsorption capacity for the removal of dye pollutants with the aid of GO sheets. More impressively, on slightly heating GHA gels in ethanol for only 30 min after adsorption, the dyes would exude from the GHA gels rapidly and subsequently dissolve in ethanol. Thus the recovered adsorbents could be reused in the next water purification cycle. These types of strong and fully physically cross-linked hydrogels prepared by such a convenient strategy are promising as efficient recyclable toxic substance adsorbents, thus meeting the demand for the newly developed soft matter requiring remarkable mechanical properties and satisfying recyclability.