Natural materials are generally damage adaptive through their multilevel architectures, with the characteristics of compositional and mechanical gradients. This study demonstrated that the desired elastic gradient can be in-situ stress-induced in a titanium alloy, and that the alloy showed extreme fatigue-damage tolerance through the crack deflection and branch due to the formation of a three-dimensional elastically graded zone surrounding the crack tip. This looks like a perceptive and adaptive mechanism to retard the crack: the higher stress concentrated at the tip and the larger elastic gradient to be induced. The retardation is so strong that a gradient nano-grained layer with a thickness of less than 2 μm formed at the crack tip due to the highly localized and accumulated plasticity. Furthermore, the ultrafine-grained alloy with the nano-sized precipitation also exhibited good damage tolerance.