The shot peening process is one of the surface treatments. In this process the peening effects are characterized by the fact that the surface layer undergoes large plastic deformation due to the collision of shots. The effects are greatly influenced by the processing history or the thermal history of material. Little is known about the relation between hardness of the shot peened surface and the processing history of materials. In the present study, the effect of heating and subsequent re-shot peening on the surface characteristics of the shot-peened carbon steel was investigated. Shot peening was performed with an air-type machine using cast steel balls. Hardness and compressive residual stress in the re-shot peened workpieces were measured. When the heat treated workpiece was re-processed by shot peening, surface hardness and fatigue life of carbon steel were improved. It was found that the surface characteristics of the peened carbon steel were improved by heating and subsequent re-shot peening.