Magnesium-based hydrogen storage powders were prepared by reactive milling under hydrogen atmosphere. The crystallitic carbon, prepared from anthracite coal by demineralization and carbonization, was used as milling aid and synergic hydrogen storage additive of magnesium. Dispersive powders of particle size about 20 to 60 nm and hydrogen capacity of 4.78 wt.% were prepared from magnesium with 40 wt.% of crystallitic carbon by 3 h of milling under 1 MPa of hydrogen atmosphere. The hydrogen stored in carbon increased with the addition of Al, Mo, Co and Fe. FT-IR showed that the carbon atoms at the edges of crystallitic carbon particles were hydrogenated into C-H during reactive milling with hydrogen. The initial dehydrogenation temperature of hydrogen-storage material 60Mg40C is 275.8 °C, and its dehydrogenation plateau pressure at 300 °C is 0.2 MPa and the length of the plateau is 5.0 wt.% of hydrogen capacity.