Protein-based hydrogels usually do not exhibit high stretchability or toughness, significantly limiting the scope of their potential biomedical applications. Here we report the engineering of a chemically cross-linked, highly elastic and tough protein hydrogel using a mechanically extremely labile, de novo-designed protein that assumes the classical ferredoxin-like fold structure. Due to the low mechanical stability of the ferredoxin-like fold structure, swelling of hydrogels causes a significant fraction of the folded domains to unfold. Subsequent collapse and aggregation of unfolded ferredoxin-like domains leads to intertwining of physically and chemically cross-linked networks, entailing hydrogels with unusual physical and mechanical properties: a negative swelling ratio, high stretchability and toughness. These hydrogels can withstand an average strain of 450% before breaking and show massive energy dissipation. Upon relaxation, refolding of the ferredoxin-like domains enables the hydrogel to recover its massive hysteresis. This novel biomaterial may expand the scope of hydrogel applications in tissue engineering.