Since fretting fatigue damage accumulation occurs over relatively small volumes, the role of the microstructure is quite significant in fretting fatigue analysis. The heterogeneity of discrete grains and their crystallographic orientation can be accounted for using continuum crystallographic cyclic plasticity models. Such a constitutive law used in parametric studies of contact conditions may ultimately result in more thorough understanding of realistic fretting fatigue processes. The primary focus of this study is to explore the influence of microstructure as well as the magnitude of the normal force and tangential force amplitude during the fretting fatigue process. Fretting maps representing cyclic plastic strain behaviors are also developed to shed light on the cyclic deformation mechanisms.