Here we report the extraordinary thermal stability of Mg rich bimetallic nanoparticles (NPs), which is important for hydrogen storage technology. The enhanced NP stability is accomplished because of two critical improvements: (i) no void development within NPs (nanoscale Kirkendall effect) during their formation and (ii) suppressed Mg evaporation and NP hollowing during Mg hydrogenation at elevated temperature. The mechanism leading to the improved thermal stability of Mg-based bimetallic NPs is shown to be due to MgH2 hydride formation before evaporation can take place. These findings were tested for various compositions of Mg with Ni, Cu, and Ti, which are interesting combinations of materials for hydrogen storage systems. To achieve this we first demonstrate the synthesis mechanism of Mg-Ni and Mg-Cu NPs, which is well controlled at the single particle level, in order to accomplish multi-shell, alloy and intermetallic structures of interest for hydrogen storage tests. Aberration corrected transmission electron microscopy was carried out to unravel the detailed atomic structure and composition of the bimetallic NPs after production, processing, and hydrogenation. Finally, a simple and effective methodology is proposed for tuning the composition of the Mg-based bimetallic NPs based on the temperature-dependent nucleation behavior of NPs in the gas-phase.