It is commonly proposed that the fatigue strength can be enhanced by increasing the tensile strength, but this conclusion needs to be reconsidered according to our study. Here a recrystallized α-Cu-15at.%Al alloy with moderate grain size of 0.62 μm was fabricated by cold rolling and annealing, and this alloy achieved exceptional high fatigue strength of 280 MPa at 10(7) cycles. This value is much higher than the fatigue strength of 200 MPa for the nano-crystalline counterpart (0.04 μm in grain size) despite its higher tensile strength. The remarkable improvement of fatigue strength should be mainly attributed to the microstructure optimization, which helps achieve the reduction of initial damage and the dispersion of accumulated damage. A new strategy of "damage reduction" was then proposed for fatigue strength improvement, to supplement the former strengthening principle. The methods and strategies summarized in this work offer a general pathway for further improvement of fatigue strength, in order to ensure the long-term safety of structural materials.