The applicability of three-axis plane-strain compression for grain refinement and improving the properties of iron aluminum alloy (Fe–16Al–5Cr–1Mo–0.1Zr at.%) has been studied. Particular attention was paid to evolution of the microstructure with respect to effective strain and mechanical properties under tensile load, as well as the factors that influence cracking. The obtained results showed that the multi-axis compression in the MaxStrain system, as a method of severe plastic deformation, is capable of refining the grain size in the Fe–16Al–5Cr–1Mo–0.1Zr (at.%) alloy to about 500 nm without affecting significantly the initial shape of the specimen with constrained ends. The deformation of the investigated alloy at RT with the strain to 2.7 is not enough to form an ultrafine-grained structure. This kind of homogeneous structure could only be obtained through the high temperature (600 °C) processing with a very large strain ( = 30.0). The ultrafine-grained structure was formed after deformation at 600 °C with the application of 67 passes ( = 30), and exhibited high ultimate tensile strength (UTS 880 MPa) with an elongation to failure of about 0.8%. In addition, it demonstrated a dimple fracture that was in contrast to its micro-sized grained counterparts with moderate UTS (550–750 MPa) and good elongation to failure (6–9%), but brittle fracture.