Accurate measurement of residual stress is necessary to obtain reliable predictions of fatigue lifetime and enable estimation of time-to-facture for any given stress level. In this article, relaxation of welding residual stresses as a function of cyclic loading was documented on three common steels: AISI 1008, ASTM A572, and AISI 4142. Welded specimens were subjected to cyclic bending (R = 0.1) at different applied stresses, and the residual stress relaxation existing near the welds was measured as a function of cycles. The steels exhibited very different stress relaxation behaviors during cyclic loadings, which can be related to the differences in the microstructures of the specimens. A phenomenological model, which treats dislocation motion during cyclic loading as being analogous to creep of dislocations, is proposed for estimation of the residual stress relaxation.