In this paper, we present the first numerical analysis upon the effect of heterogeneity on the stresses in fretting fatigue problems. We analyze the stress distribution in heterogeneous material under fretting fatigue loading condition based on Direct Numerical Simulations (DNS) in solid mechanics. The heterogeneity is introduced to the fretting fatigue specimen using two models based on micro-voids, namely a single hole cell model and a four hole cell model. From this study, it is found that the effect of heterogeneity is more significant in shear stress than in normal stress due to more complex loading after applying the fatigue cycle. Moreover, the numerical results indicate that the peak shear stress is shifted from the interface in case of homogeneous material, to the micro-voids in case of heterogeneous material.