The depth distribution of the residual stress in graded (Ti, Al) N coating deposited on steel by arc ion plating was measured by the Stripping Layer Substrate Curvature Technique, and the effect of graded (Ti, Al) N and mono-layered (Ti, Al)N coating on the fatigue properties of 1Cr11Ni2W2MoV stainless steel were investigated. The depth distribution of the residual stress in mono-layered Ti70Al30N and TiN were also measured for comparison. The results show that the residual stresses in the coatings are compressive, which increase gradually from the coating/substrate interface and reach a maximum value at the middle region, then decrease until the surface. Compared with TiN and Ti70Al30N, the stress maximum value in the graded coating is nearer to the coating surface. It is also shown that the fatigue strength of the graded (Ti, Al)N and Ti70Al30N coated samples are superior to that of the uncoated substrate. The improvement of the fatigue properties for the coated samples is thought to be attributed to the hard coatings with high compressive stress.