Surface hardening procedures such as mechanical shot peening and deep cold rolling introduce extensive surface cold work and compressive residual stress. While both methods are designed to increase material fatigue strength, single crystal nickel-based superalloys used for turbine blade applications are routinely exposed to temperatures above 900 °C. The thermal stability of the cold work and the residual stress induced in the sub-surface of the material is therefore a key design requirement. In this study, mechanically shot peened and deep cold rolled samples of the superalloy CMSX-4 were annealed in vacuum at either 900 °C or 1100 °C for between 100 and 1000 h. Using scanning electron microscopy, electron backscattered diffraction and centre hole drilling, the cold work, the residual stress and the material response to annealing heat treatments were all studied. Significant recrystallisation of the cold worked material was observed, typically after 500 h at 900 °C and after 5 h at 1100 °C. Undesirable topologically close-packed precipitates began forming on slip bands generated by both surface hardening techniques after only 10 h at 900 °C, whereas at 1100 °C their formation was hindered by the recovery of slip bands. Rafting of the γ/γ' microstructure took place at 1100 °C, with the extent of the rafting found to be limited by the depth of compressive residual stress. Samples treated by deep cold rolling generally displayed smaller recrystallisation depths, lower rates of topologically close-packed precipitate formation and deeper rafting than those treated by mechanical shot peening.