Mg-based nanostructured materials with a composition of Mg85Ni15-xMx (M=Y, La, or Pd) have been fabricated by proper alloying additions and controlling the crystallization process of melt spun metallic glass ribbon. XRD suggests that the average crystallite sizes range from 100 nm in the binary materials to <30 nm in the ternary alloys. Hydrogen absorption/desorption measurements show improved properties compared to nanocrystalline alloys fabricated using other processing strategies. Surface treatment of the binary and Pd-containing ribbons by ball milling or submersion in aqueous NH4+ allows the materials to be activated at 473 K, significantly lower than conventional Mg-based hydrogen storage materials. Y and La additions improve the maximum storage capacity. Absorption kinetics are also improved the materials is alloyed with La, while Y slows the reaction kinetics. Some degradation in storage capacity is observed when the materials are exposed to a cyclic absorption/desorption process, likely due to microstructural coarsening. The Mg85Ni10Pd5 composition fully absorbs and desorbs ≈5 wt. % H at 473 K, while other bulk Mg-based materials require temperatures in excess of 573 K.