Relaxation behavior of residual stress and its effect on fretting fatigue response of shot-peened titanium alloy, Ti-6A1-4V were investigated at room and elevated temperatures under constant amplitude cycling condition using two contact configurations, cylinder on flat and flat on flat. Measurements by X-ray diffraction method before and after tests showed that residual compressive stress relaxed during fretting fatigue. Fretting fatigue life depended on the amount of stress relaxation as well as on the applied stress range. Elevated temperature induced more residual stress relaxation relative to that at room temperature, which, in turn, resulted in a reduction of fretting fatigue life. There was no effect of contact geometry on fretting fatigue life on the basis of the applied cyclic stress on the specimen, which did not account for any effects from contact stresses, even though less residual stress relaxation occurred with flat pad. A critical plane based fatigue crack initiation model, modified shear stress range parameter (MSSR), was computed from finite element analysis for tests incorporating various levels of stress relaxation. It showed that not only crack initiation but also crack propagation should be considered to characterize fretting fatigue behavior of shot-peened specimens.