Mg-based nanostructured hydrides have been synthesized by ball milling using two alternative approaches. The first is based on the reactive milling of Mg powders in H-2 atmosphere, while the second on the milling of commercial MgH2 powders under inert atmosphere. In both cases 10 wt.% of Fe was added to the powder mixture, with the aim of introducing a catalyst agent. The microstructural characterization was carried out by X-ray diffraction, and both scanning and transmission electron microscopy. Hydrogen desorption behavior was evaluated by differential scanning calorimetry. Almost full hydrogenation of pure Mg powders can be achieved by reactive milling. Catalyst addition strongly accelerates the hydride formation. Both reactive milling of Mg powder and inert gas milling of MgH2 induce a nanosized microstructure with similar H-desorption behavior. The role played by Fe becomes particularly evident in H-desorption. In fact, a temperature decrease of about 100degreesC was found in samples having the same crystallite size and similar powder morphology.