Investigation on the quasi-static residual stress relaxation is an important aspect of component design and life management. After taking into account the influence of transverse stress and strength distribution, this paper proposes a new criterion of residual stress relaxation under quasi-static load as follow: the surface residual stress tends to relax as long as the Mises effective stress anywhere exceeds the local yield point. In addition, by X-ray tensile test, a method of determining superficial yield strength based on the Von Mises hypothesis was applied at the shot-peened surface of a martensitic stainless steel 0Cr13Ni4Mo. The experimental results show that the yield strength of superficial layer is larger than that of core material. According to the experimental results, a simplified ladder-shaped model of the depth distribution of yield strength is proposed. On the basis of the above-mentioned relaxation criterion and the strength distribution model, a new method is presented to calculate the relaxation amount. The calculated results coincide with the experimental results.