Hydrogen storage in solid hydrides is the most attractive method of on-board hydrogen storage in fuel cell for cars. Mg metal exhibits a high-storage capacity by weight and has been considered a group of potentially attractive candidates for solid-state hydrogen storage. In this study, mechanochemical synthesis of nanocrystalline Mg-based hydrogen storage composites from various starting materials in specialized hydrogen ball mills has been achieved. The reactive synthesis process and the hydrogen desorption behaviors of the composite hydrides were investigated by X-ray diffraction (XRD), thermogravimetric and differential scanning calorimetry (TG-DSC). The results show that nano-sized MgH2 and Mg(AlH4)2 could be directly synthesized by pure Mg and pretreated Al powder, as well as Mg-Li-Al alloy powder. Alloying element Li could remarkably promote the synthesis of magnesium alanate, the product composite hydrides releasing 6.2wt% H2 through multi-step decompositions, of which the starting endothermic peaks are as low as 65°C.