The primary objective of this work was to determine the influence of 1–4 at% Zr additions on the thermal stability of mechanically alloyed nanocrystalline Fe–Cr alloys containing 10 and 18 at% Cr. Grain sizes based on XRD, along with microhardness changes, are reported for isochronal annealing treatments up to 1000 °C. Microstructure investigations were done using optical microscopy, channeling contrast FIB imaging, and TEM. Grain size stabilization in the nanaoscale range was maintained up to 900 °C by adding 2 at% Zr. Kinetic pinning by nanoscale intermetallic particles was identified as one source of high temperature grain size stabilization. Intermetallic particles also contribute to strengthening in addition to the Hall–Petch effect. The analysis of microhardness, XRD data, and measured values from the TEM image for Fe-10 at% Cr with 2 at% Zr suggested that both thermodynamic and kinetic mechanisms would contribute to grain size stabilization. There was no significant difference in the results for the 10 and 18 at% Cr alloys, which indicates that the α→γ transformation does not influence the grain size stabilization.