To study the fatigue properties of TC4 titanium alloy subjected to compound strengthening treatment by laser shock peening and shot peening, surface residual stress and cut-off value of detail fatigue rated strength (DFR_cutoff) were measured for TC4 titanium alloy for various surface-strengthening cases. These cases included untreated state, shot peening, laser shock peening, and compound strengthening by shot peening and laser shock peening. Additionally, the distribution of residual stress was analyzed by ABAQUS software. Test results show that samples treated by compound strengthening exhibit the highest values of both the surface residual compressive stress and DFR_cutoff, with an increment of 189.1% and 62.3% over those of untreated samples, respectively. Simulation results indicate that residual compressive stress can form on the sample surface after the strengthening process, and the surface residual compressive stress on the compound-strengthened surface is the highest, followed by the samples subjected to shot peening and laser shock peening. Moreover, the residual compressive stress layer created by the compound strengthening treatment is the deepest, followed by that for laser shock peening and finally shot peening. From the combined results of tests and finite element analysis, it can be concluded that the DFR_cutoff of TC4 titanium alloy is positively correlated with the surface residual compressive stress and depth of the residual compressive stress layer.