Nanostructuring of bulk metals is now well documented with the development of severe plastic deformation (SPD) for improving the physical and mechanical properties of engineering materials. Processing by high-pressure torsion (HPT), which was developed initially as a grain refinement technique, was extended recently to the mechanical bonding of dissimilar metals during nanostrcturing which generally involves significant microstructural heterogeneity. Here we introduce, for the first time, a bulk metastable Al-Mg supersaturated solid solution by the diffusion bonding of separate Al and Mg metal solids at room temperature using HPT. Exceptional hardness was achieved homogeneously throughout the metastable alloy with a record maximum supersaturated Mg content of ~38.5 at.% in the Al matrix having a grain size of ~35-40 nm. Our results demonstrate the synthesis of a bulk nanocrystalline metastable alloy with good microstructural stability at room temperature where such bulk solids are not yet reported for mechanical alloying by powder metallurgy.