The irreversible damage at cracks during the fatigue of crystalline solids is well known. Here we report on in situ high-energy x-ray evidence of reversible fatigue behavior in a nanocrystalline NiFe alloy both in the plastic zone and around the crack tip. In the plastic zone, the deformation is fully recoverable as the crack propagates, and the plastic deformation invokes reversible interactions of dislocation and twinning in the nanograins. But around the crack tip lies a regime with reversible grain lattice reorientation promoted by a change of local stress state. These observations suggest unprecedented fatigue deformation mechanisms in nanostructured systems that are not addressed theoretically.