The present work aims to investigate (i) the feasibility of formation of Fe-7Cr-xZr and Fe-15Cr-xZr (x = 0.25, 0.5 and 1 at%) disordered solid solutions by mechanical alloying (MA) and (ii) their thermal stability and mechanical properties of spark plasma sintered (SPSed) samples. Effect of Zr addition on phase evolution in Fe-Cr-Zr alloy and its influence on their thermal stability and mechanical properties (microhardness and compression strength) have been studied in detail. Transmission electron microscopy-selected area diffraction pattern (TEM-SAED) and X-ray diffraction (XRD) phase analysis confirm the formation of complete solid solution after 25 h of MA. Grain size was observed to stabilize significantly within nanometer range after annealing at 600–1200 °C. The SPSed (at 1000 °C) samples showed the best combination of hardness (9.4 GPa) and compressive strength (ultimate compressive strength-2200 MPa and yield strength-1800 MPa) corresponding to an average grain size of<100 nm. This is due to the strengthening mechanisms of grain boundary strengthening (owing to solute segregation and solute drag effect), precipitation hardening (Zener pinning) by Fe2Zr phase and excellent densification achieved by SPS.