Fretting wear damage of high-strength titanium fasteners has caused a large number of disastrous accidents. Traditionally, it is believed that both high strength and excellent ductility can reduce fretting wear damage. However, whether strength and ductility are contradictory or not and their appropriate matching strategy under the external applied normal stress (F_w) are still confusing problems. Here, by analyzing the subsurface-microstructure deformation mechanism of several samples containing various α precipitate features, for the first time, we design strategies to improve fretting damage resistance under different matching relation between F_w and the tensile strength of materials (R_m). It is found that when F_w is greater than R_m or F_w is nearly equivalent to R_m, the deformation mechanism mainly manifests as serious grain fragmentation of β and α_GB constituents. Homogeneous deformation in large areas only reduces damage to a limited extent. It is crucial to improve the strength to resist cracking and wear, but it is of little significance to improve the ductility. However, when F_w is far less than R_m, coordinated deformation ability reflected by ductility plays a more important role. The deformation mechanism mainly manifests as localized deformation of β and α_GB constituents (kinking induced by twinning and spheroidizing). A unique composite structure of nano-grained/lamellar layer and localized deformation transition layer reduces fretting damage by five times compared with a single nano-grained layer. Only when the strength is great enough, improving the plasticity can reduce wear. This study can provide a principle for designing fretting damage resistant alloys.