In order to improve the hydrogen storage characteristics of magnesium, both chemical alloying by Nb and mechanical alloying (MA) of (Mg+10 wt.%Nb) and (MgH2+10 wt.%Nb) powder mixtures were investigated, with particular attention paid to their structural stability. Extensive powder refinement was noted for both compositions within 20 h of milling at 250 rpm. Even nano-sized particles were generated in the hydride mixture. XRD and Rietveld analyses show the formation of a bcc phase in each case. The amount of the bcc phase increases with increasing milling time to the detriment of Nb. For the (Mg+10 wt.%Nb) mixture, it is confirmed that the newly formed phase is a bcc-(Nb,Mg) solid solution, with an extended solubility of Nb in Mg. However, for the (MgH2+10 wt.%Nb) powder mixture, the new bcc phase can be a Nb hydride (NbHx, x<1.0), or a bcc-(Nb,Mg) solid solution, or a (Nb,Mg)Hx solid solution, or even a mixture of the three.