Fatigue tensile treatment was performed on 00Cr12 heat-resistant steel specimens which had been treated by laser shock processing (LSP). The unilateral tolerance factor statistical analysis method and the two-dimensional Weibull distribution method were used to predict the values of fatigue safe lives of the specimens respectively. The results indicate that the fatigue lives of 00Cr12 specimens were enhanced greatly after LSP, and improved by 62% compared with the specimens which were not treated by LSP. The unilateral tolerance factor method obtained an exact estimation value of the fatigue safe life; while the two-dimensional Weibull distribution method can get a range of values of fatigue safe lives, the fatigue safe lives of the specimens which after LSP were a range from 116570 to 150230, the average value was 132330. The two-dimensional Weibull distribution method has more engineering applicability and can be used to estimate the fatigue safe lives with fewer experiments.