The onset of fretting fatigue is characterized by material microstructural changes in which the extent of the damage is comparable to grain size, and hence, the microstructure characteristics could have a significant effect on fatigue crack initiation. In this paper, a three-dimensional finite element crystal plasticity framework is presented for simulation of the fretting fatigue. Controlled Poisson Voronoi tessellation (CPVT) method is employed to generate the polycrystalline region. In the CPVT method, regularity parameter controls the shape of grains. In this study, the impact of grain size and regularity parameter on crack initiation life and initiation site has been investigated. Cumulative plastic slip was used as a parameter of microstructure-sensitive fatigue indicator. This parameter could effectively predict the location of crack initiation and its life. The results show that regularity parameter has a significant effect on the location of crack initiation. Furthermore, the effect of grain size on the fretting fatigue life of 316L stainless steel was investigated experimentally through testing different specimens with different grain sizes, to validate the simulation results. © 2018 Wiley Publishing Ltd.