The stability of residual stress plays an important role in the fatigue performance of materials. In this work, the stability of surface residual stress in carburized alloy steel with different carburized layers is studied by axial fatigue tests. Different stress amplitudes are applied to the specimens over several cycles, and the resulting residual stress on the surface is measured by X-ray diffraction. It is found that residual stress relaxation occurs on the specimens when the applied stress amplitude is large, and that the relaxation rate depends on the magnitude of the stress amplitude. The stress relaxation is most obvious in the first cycle, and changes slowly in the subsequent cycles. A model of surface residual stress evolution is established which can accurately describe the relaxation process. The residual stress on the surface of the specimen is found to be in a stable state, if the stress amplitude is less than 30% of the material yield strength.