The adhesion of soft connective tissues (tendons, ligaments, and cartilages) on bones in many animals can maintain high toughness (∽800 J m-2) over millions of cycles of mechanical loads. Such fatigue-resistant adhesion has not been achieved between synthetic hydrogels and engineering materials, but is highly desirable for diverse applications such as artificial cartilages and tendons, robust antifouling coatings, and hydrogel robots. Inspired by the nanostructured interfaces between tendons/ligaments/cartilages and bones, we report that bonding ordered nanocrystalline domains of synthetic hydrogels on engineering materials can give a fatigue-resistant adhesion with an interfacial fatigue threshold of 800 J m-2, because the fatigue-crack propagation at the interface requires a higher energy to fracture the ordered nanostructures than amorphous polymer chains. Our method enables fatigue-resistant hydrogel coatings on diverse engineering materials with complex geometries. We further demonstrate that the fatigue-resistant hydrogel coatings exhibit low friction and low wear against natural cartilages.