The synergetic effect of shot peening (SP) and laser shot peening (LSP) on the fatigue behavior of a medium carbon steel was investigated. A fatigue life transition was observed in the S-N curve, where the fatigue performance of the SP + LSP specimen was improved only at lower stress levels. This result is consistent with the short crack propagation behavior observed in the near-threshold region. The heterogeneous structures comprised by ultra-fine grains, dislocation tangles, and more high-angle grain boundaries were responsible for this behavior which effectively retard the short crack propagation