In this paper, the thermal stability of cryomilled nanocrystalline (NC) AZ31 powder was evaluated by annealing at elevated temperature ranging from 350 to 450 °C. The results show the NC AZ31 powder exhibited excellent thermal stability during short anneals at 350–450 °C, and the mechanisms were investigated in detail. There were two separate growth stages with a transition point at around 400 °C. More specifically, between 350 and 400 °C, NC Mg grains were stable at approximately 32 nm, even after 1 h annealing. At 450 °C, the nano grains grew to 37 nm in the first 5 min and grew quickly to approximately 60 nm after 15 min. However, the grain growth was limited when the annealing time was increased to 60 min. The average grain size remained stable less than approximately 60 nm even after long anneals at temperatures as high as 450 °C (0.78 T/TM), indicating an outstanding degree of grain size stability. This excellent thermal stability can be mainly attributed to solute drag and Zener pinning.