Electrodeposited nanocrystalline (nc) metal is often used as a model material in nc material investigation. But electrodeposition typically yields only thin foils that are at most several hundred micrometers in thickness, this arouses experimental difficulties in fatigue testing. There are several investigations on fatigue of electrodeposited nc metals. However, for the lack of direct experimental evidence, the mechanism of fatigue crack nucleation for nc materials is still not clear. In addition to fatigue properties, the microstructure stability is another key point for the practice of bulk nc materials. Some research papers indicated that the grains of nc metal would grow up under quasi--static loading, but no any investigation give out results under cyclic loading. In this paper, fatigue of electrodeposited nc Ni was experimentally investigated. Fatigue testing was carried out to obtain the S--N curves. For the reason that surface is the most important site for fatigue crack initiation, atomic force microscopy (AFM) was used to scan the sample surface before and after fatigue testing, which provides a direct observation on fatigue crack nucleation mechanism. For investigation on the stability of microstructure, the AFM was also used to measure the grain size of samples after fatigue loading, and nanoindenter was used to investigate the change of mechanical properties of samples after fatigue testing. The S--N curves indicate that nanocryatalline samples have a higher fatigue limit than coarse grain ones. The AFM images indicate that cell pellet morphology with the average size of 73 nm appeared on sample surface after high cycle fatigue testing and the grain size is the same as those before the fatigue testing. From the results of nanoindentation, the mechanical properties including hardness, strain rate sensitivity and elastic modules of samples also keep no obvious change after fatigue loading. Based on these results, the fatigue crack nucleation mechanism of electrodeposited nc Ni was discussed.