In this work we report strategies to nucleate bimetallic nanoparticles (NPs) made by gas phase synthesis of elements showing difficulty in homogeneous nucleation. It is shown that the nucleation assisted problem of bimetallic NP synthesis can be solved via the following pathways: (i) selecting an element which can itself nucleate and act as a nucleation center for the synthesis of bimetallic NPs; (ii) introducing H-2 or CH4 as an impurity/trace gas to initiate nucleation during the synthesis of bimetallic NPs. The latter can solve the problem if none of the elements in a bimetallic NP can initiate nucleation. We illustrate the above mentioned strategies for the case of Mg based bimetallic NPs, which are interesting as hydrogen storage materials and exhibit both nucleation and oxidation issues even under ultra-high vacuum conditions. In particular, it is shown that adding H2 in small proportions favors the formation of a solid solution/alloy structure even in the case of immiscible Mg and Ti, where normally phase separation occurs during synthesis. In addition, we illustrate the possibility of improving the nucleation rate, and controlling the structure and size distribution of bimetallic NPs using H-2/CH4 as a reactive/nucleating gas. This is shown to be associated with the dimer bond energies of the various formed species and the vapor pressures of the metals, which are key factors for NP nucleation.