Although severe plastic deformation (SPD) alters the microstructure and phase transformation at the early stages of straining, the microstructural features finally saturate to the steady states at large shear strains. However, from the atomic point of view, to achieve the steady state in immiscible systems with positive heat of mixing, the minimum shear strain should be so high that the thickness of sheared phases becomes comparable to one atomic distance. In this study, ultrahigh shear strains up to ~70,000 are introduced in different Mg-based immiscible systems by high-pressure torsion (HPT) method for up to 1500 turns. New metastable phases are formed in most of the selected magnesium alloys by ultra-SPD, in good agreement with the first-principles calculations. However, the microstructural/structural saturation hardly occurs in many alloys even at ultrahigh strains. The materials processed by ultra-SPD exhibit unique hardness-strain and tensile behaviors which cannot be observed after conventional SPD.