Fatigue failure is invariably the most crucial failure mode for metallic structural components. Most microstructural strategies for enhancing fatigue resistance are effective in suppressing either crack initiation or propagation, but often do not work for both synergistically. Here, we demonstrate that this challenge can be overcome by architecting a gradient structure featuring a surface layer of nacre-like nanolaminates followed by multi-variant twinned structure in pure titanium. The polarized accommodation of highly regulated grain boundaries in the nanolaminated layer to cyclic loading enhances the structural stability against lamellar thickening and microstructure softening, thereby delaying surface roughening and thus crack nucleation. The decohesion of the nanolaminated grains along horizonal high-angle grain boundaries gives rise to an extraordinarily high frequency (≈1.7 × 10³ times per mm) of fatigue crack deflection, effectively reducing fatigue crack propagation rate (by 2 orders of magnitude lower than the homogeneous coarse-grained counterpart). These intriguing features of the surface nanolaminates, along with the various toughening mechanisms activated in the subsurface twinned structure, result in a fatigue resistance that significantly exceeds those of the homogeneous and gradient structures with equiaxed grains. Our work on architecting the surface nanolaminates in gradient structure provides a scalable and sustainable strategy for designing more fatigue-resistant alloys.