Laser shock processing (LSP) is carried out on K403 nickel-based alloy turbine blades and the high temperature high and low cycle complexed fatigue tests are conducted to verify the reinforcement effect. The results of the fatigue experiments show that a greater flatness area near the fatigue crack initiation (FCI) is induced by LSP, the fatigue striation spacing on the fatigue crack growth (FCG) area decreases and lots of second cracks are generated after LSP. Grain refinement and high residual compressive stress on the surface layer are induced by LSP. But when the K403 nickel-based alloy after LSP is subjected to heat treatment at 550 ℃ for 150 min, a part of residual compressive stress has got relaxation while the refined structure has still remained good thermal stability. Compared with the untreated samples, the fatigue life of turbine blades is increased by 140% after LSP. The grain refined structure and residual compressive stress after relaxation are the main causes of improvement of nickel-based alloy fatigue life.