Severe plastic deformation of a Mg-Al-Ca alloy resulted in different types of grain structure. High pressure torsion (HPT) was shown to lead to the formation of a nanocrystalline structure with a grain size of 100-200 nm, while equal channel angular pressing (ECAP) produced ultrafine grained (UFG) or submicrocrystalline (SMC) structures, depending on the ECAP temperature. An UFG structure with a grain size of 2-5 -m was formed at 300°C, as distinct from a finer SMC structure with a grain size of 300-800 nm formed at a lower temperature (220°C). The possibility of increasing the strength of the alloy in the UFG condition by a factor of 1.5-2, combined with a reasonable level of ductility and enhanced functional properties was thus demonstrated. ECAP of annealed Mg-Al-Ca with the formation of UFG structure was shown to lead to increased yield strength (by a factor of 2) and enhanced tensile ductility (by a factor of 3).