Theoretical modeling suggests that the grain size remains unchanged during fatigue crack growth in nanocrystalline metals. Here we demonstrate that a modulated structure is generated in a nanocrystalline Ni-Fe alloy under cyclic deformation. Substantial grain coarsening and loss of growth twins are observed in the path of fatigue cracks, while the grains away from the cracks remain largely unaffected. Statistical analyses suggest that the grain coarsening is realized through the grain lattice rotation and coalescence and the loss of growth twins may be related to the detwinning process near crack tip.