We investigated the strengthening mechanism of laser shock processing (LSP) at high temperatures in the K417 nickel-based alloy. Using a laser-induced shock wave, residual compressive stresses and nanocrystals with a length of 30–200 nm and a thickness of 1 μm are produced on the surface of the nickel-based alloy K417. When the K417 alloy is subjected to heat treatment at 900 °C after LSP, most of the residual compressive stress relaxes while the microhardness retains good thermal stability; the nanocrystalline surface has not obviously grown after the 900 °C per 10 h heat treatment, which shows a comparatively good thermal stability. There are several reasons for the good thermal stability of the nanocrystalline surface, such as the low value of cold hardening of LSP, extreme high-density defects and the grain boundary pinning of an impure element. The results of the vibration fatigue experiments show that the fatigue strength of K417 alloy is enhanced and improved from 110 to 285 MPa after LSP. After the 900 °C per 10 h heat treatment, the fatigue strength is 225 MPa; the heat treatment has not significantly reduced the reinforcement effect. The feature of the LSP strengthening mechanism of nickel-based alloy at a high temperature is the co-working effect of the nanocrystalline surface and the residual compressive stress after thermal relaxation.