A heterogeneous fatigue peridynamic model will be proposed to predict the nucleation and propagation of cracks. To reduce the costly calculations for fatigue simulations, an implicit solver will be introduced for fatigue simulations. Voronoi tessellation will be used in the fatigue peridynamic model to investigate the influences of grain size, grain orientation, grain boundary strength coefficient on the fatigue behaviours.