The effects of different carbon additives: carbon black, graphite and multi-walled carbon nanotubes, on the hydrogen storage properties of magnesium were investigated and compared. Samples of Mg containing 5 wt.% additive were prepared by milling in hydrogen gas using a magnetically controlled ball mill. Structural and phase evolution were investigated using X-ray diffractometry (XRD) and morphology and microchemistry by scanning electron microscopy (SEM) with energy dispersive X-ray spectroscopy (EDS). Raman spectroscopy was used to investigate changes in the nature of carboncarbon bonding, differential scanning calorimetry (DSC) to investigate desorption characteristics, and thermogravimetry (TG) to estimate the hydrogen storage capacity of both milled and rehydrogenated samples. There was no significant difference in the hydrogen storage capacity between the as-prepared (6.4 wt.%) and rehydrogenated (6.2 wt.%) composites, however, the rehydrogenated composite containing graphite displayed a remarkable decrease in the desorption temperature, a result which wants further investigation.