Notched fatigue samples were designed to approximate a typical leading edge of the blade with foreign object damage (FOD) in order to study the anti-fatigue performance of FOD-blades with laser shock processing (LSP). The surface at the crack tip of the notches of TC17 fatigue samples was LSPed with double sides. A YAG laser system was used with laser energy of 30 J, pulse width of 15 ns and square spot of 4 mm×4 mm. The residual stress, microstructure, fatigue performance and fatigue fracture of samples with and without LSP were measured and analyzed by X-ray diffractometer, Transmission Electron Microscope (TEM), high-frequency fatigue tester and Scanning Electron Microscope (SEM). Compared with the notched fatigue samples without LSP, the surface residual stresses of LSP-TC17 alloy increased to -445MPa. High density dislocation, twin and nanocrystallite were formed in the surface. The fatigue strength of LSP-TC17 notched fatigue samples increased by 55.6%. Fatigue strengthening mechanism of TC17 notched fatigue samples was high amplitude compressive residual stress and surface nanocrystallite. The experiment results lay the theoretical foundation and provide the technological reference for LSP-FOD blades.