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 (Fw) 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 Fw and the tensile strength of materials (Rm). It is found that when Fw is greater than Rm or Fw is nearly equivalent to Rm, 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 Fw is far less than Rm, 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.