Influence of shot peening media on fatigue performance of the high-strength wrought magnesium alloy AZ80 has been investigated at Almen intensities ranging from 0.04 to 0.4 mmN. By the use of different peening media (including glass beads, Zirblast B30 and Ce-ZrO₂ (ZrO₂ beads stabilized by Ce)), the improvement of about 60-75% in fatigue strength was achieved at optimum conditions. Peening AZ80 with Ce-ZrO₂ shots resulted in the fewest surface defects, lowest roughness, highest maximum compressive residual stress and highest improvement of fatigue strength. A pronounced overpeening effect was observed when glass beads or Zirblast B30 shots were used as peening media. In contrast, specimens shot-peened by Ce-ZrO₂ shots exhibited an extremely broad process window, i.e. the overpeening effect disappeared.