Martensitic stainless steel AISI 420 was mechanically surface treated (deep rolled). Fatigue performance was evaluated using S/N curves. Residual stress and work hardening state relaxations during annealing and cyclic loading were investigated. Annealing processes were performed at temperature range of 300–600 °C and soaking time between 0.1–104 min. Rotary bending fatigue tests were performed at stress amplitudes of 517–600 MPa with different number of cycles. The results of this study showed that residual stresses and work hardening states were thermally relaxed during annealing processes because of recovery and recrystallization mechanisms. Zener-Wert-Avrami function was used to analyze activation enthalpies of relaxation mechanisms. During cyclic loading, residual stresses were mechanically relaxed higher than that of the work hardening states.