Hydrogel-based devices are widely used as flexible electronics, biosensors, soft robots, and intelligent human-machine interfaces. In these applications, high stretchability, low hysteresis, and anti-fatigue fracture are essential but can be rarely met in the same hydrogels simultaneously. Here, we demonstrate a hydrogel design using tandem-repeat proteins as the cross-linkers and random coiled polymers as the percolating network. Such a design allows the polyprotein cross-linkers only to experience considerable forces at the fracture zone and unfold to prevent crack propagation. Thus, we are able to decouple the hysteresis-toughness correlation and create hydrogels of high stretchability (~1100%), low hysteresis (< 5%), and high fracture toughness (~900 J m-2). Moreover, the hydrogels show a high fatigue threshold of ~126 J m-2 and can undergo 5000 load-unload cycles up to 500% strain without noticeable mechanical changes. Our study provides a general route to decouple network elasticity and local mechanical response in synthetic hydrogels.