We have proposed the application of Mg-containing carbon nanocomposites, synthesized by high energy ball milling of graphite (G) and Mg with organic additives (tetrahydrofuran, benzene, cyclohexane, etc.), as novel hydrogen storage materials. Hydrogen storage by mechano-synthesized nanocomposites was studied, combined with characterization by XRD, TPD, DSC, TGA, TEM and Raman spectroscopy. The use of organic additives during the milling process was an important factor in determining the hydrogen-absorbing properties of the resulting nanocomposites. Besides hydriding/dehydriding by the Mg component additional hydrogen uptake by the Mg/G nanocomposites as a result of such mechanical treatments was observed.