The emerging applications of hydrogels in devices and machines require hydrogels to maintain robustness under cyclic mechanical loads. Whereas hydrogels have been made tough to resist fracture under a single cycle of mechanical load, these toughened gels still suffer from fatigue fracture under multiple cycles of loads. The reported fatigue threshold for synthetic hydrogels is on the order of 1 to 100 J/m2. We propose that designing anti-fatigue-fracture hydrogels requires making the fatigue crack encounter and fracture objects with energies per unit area much higher than that for fracturing a single layer of polymer chains. We demonstrate that the controlled introduction of crystallinity in hydrogels can substantially enhance their anti-fatigue-fracture properties. The fatigue threshold of polyvinyl alcohol (PVA) with a crystallinity of 18.9 weight % in the swollen state can exceed 1000 J/m2.