The effect of post-heat treatment on the coating characteristics and the fatigue strength of the gas flame thermally sprayed Stellite alloy coatings on $0.35\%$ carbon steel were investigated. The fatigue fracture surfaces of the heat treated samples were observed using SEM (Scanning Electron Microscopy). For as-sprayed samples, there was considerable scattering in the fatigue life due to the presence of the pores in the coating. After the post-heat treatment to improve the microstructural characteristics of the coating layer, the fatigue strength of the specimens was greatly improved, increasing with increasing the coating thickness. For the specimens with the 0.3mm and 0.5mm thick coating, the fatigue cracks originated in the substrate region just below the interface. On the contrary, for the specimens with the 1.0mm thick coating, they nucleated at the pore within the coating, and the fatigue strength was 2.6 times higher than that of the substrate due to the high fatigue resistance of the coating.