Powders of elemental Mg, Zn, Al and Ag were milled in order to produce nanocrystalline alloys with nominal composition Mg98M2 (M=Zn, Al and Ag). Pure Mg was also mechanically milled without any additions. Single-phase nanocrystalline (crystal size 24-26 nm) Mg98M2 alloys were produced after 216 ks of milling. A passivity procedure was followed immediately after milling, by gradually exposing the alloy powders to air (~ 12 hrs). After this procedure, the mechanically alloyed powders were kept under argon atmosphere before being hydrided at 200 and 300 °C under 0.5 and 3 MPa P for 10 min. Previously milled (~ 1.5 years before) and passivated powder alloys (stored in air and referred to as “AE” samples) were also hydrided under the same conditions. No hydriding was observed in the as-received Mg powders (crystal size >> 100 nm), but the as-milled, passivated nanocrystalline alloys were partially hydrided (even the AE samples). The amounts of the MgH2 phase in the hydrided samples were larger in the Ar-stored than in the AE samples under all hydriding conditions. The possible role of MgO and Mg hydroxides, as well as of the alloying elements, on the hydriding behavior of the nanostructured, mechanically alloyed powder alloys is discussed.