Water pollution caused by heavy metals has dramatically impacted ecosystems in recent years. For instance, 45.4% of lakes in China are in the category of moderate to high risk of toxic metal pollution, due to excessive mining. There is, therefore, a need for efficient techniques of metal decontamination. Hydrogels are gaining interest as heavy metal adsorbents because of their easy separation, but hydrogel applications are limited due to their poor mechanical property. Here we solve this problem by introducing natural attapulgite into the sodium alginate-poly(acrylic acid) semi-interpenetrating polymer network of the hydrogel. Results show that the compressive stress of the hydrogel with 10% attapulgite, of 1.230 Mpa, was 4.1 times higher than that of pure hydrogel, of 0.299 MPa. The adsorption capacity of hydrogel with 10% attapulgite was high, of 272.8 mg/g for Cu2+ and 391.7 mg/g for Pb2+. Even after five cycles of adsorption, the hydrogel with 10% attapulgite still adsorbs 261.7 mg/g Cu2+ and 368.1 mg/g Pb2+. Our findings thus reveal that network-structured sodium alginate-poly(acrylic acid)/attapulgite hydrogel holds great potential as an efficient and recyclable adsorbent for heavy metal removal.