The mechanical properties and structural stability of a high-pressure torsion (HPT)-induced bulk nanostructured metastable Al–Mg system were examined after natural aging at room temperature for 60 days. The sample demonstrated a high yield strength of 1.3–1.5 GPa with an excellent plasticity by achieving a high strain rate sensitivity of 0.036. The high hardness is attributed to the concurrent contributions of grain refinement and solid solution strengthening. An X-ray diffraction analysis revealed a high compositional microstrain of ~0.0202 due to the supersaturation of Mg in the Al matrix after processing. This microstrain increased to ~0.0274 after natural aging due to the heterogeneous distribution of supersaturated Mg solutes without any nucleation of a second phase, thereby demonstrating a reasonable structural stability.