TC4 titanium alloy surface is treated firstly by laser shock peening (LSP), then the shock of foreign object on the specimen edge is simulated by means of a gas gun test system, and finally the tension-tension fatigue experiment is applied to the foreign object damaged (FOD) specimen. The experimental results indicate that LSP can effectively improve the fatigue strength of FOD TC4 titanium alloy. The fatigue crack initiation (FCI) of FOD specimen without LSP locates in the notch root near the upper surface, while the FCI of FOD specimen with LSP transfers to the inside of material with a certain distance from the notch root, which makes it more difficult for crack to initiate. Numerical stress analysis results indicate that the maximum tensile stress decreases by 37.85% from 1076.2 MPa to 668.9 MPa as a result of LSP treatment. In addition, the residual tensile stress in the notch center of FOD specimen with LSP decreases by an average of 350 MPa compared with that of FOD specimen without LSP. With the loading of tension stress, in the notch of the FOD specimen with LSP, the maximum stress increases to 1124.37 MPa, in contrast, the maximum stress in FOD specimen without LSP increases to 1542.36 MPa. The former is reduced by 30.22% compared with the latter, which indicates the stress can slow the crack initiation obviously. The introduction of residual stress is one of the main reasons why LSP can improve the fatigue strength of the FOD specimen.