The hydrogen storage performances of Mg-C nanocomposites have been studied on materials synthesized by ball milling with and without addition of an organic additive. The main purpose of this work is to study in more detail the cooperative effect observed when both graphite and benzene are added to the milled blend. In fact, when both components are added to Mg in the ball milling process, good catalyzing properties of the composite surface allow improved sorption-desorption behavior of the synthesized material. The processed materials have been characterized by XRD to assess the details of the phase structure by Rietveld analysis, while surface features have been studied by XPS, which evidences structural modifications of both the surface Mg oxide and the graphite particles. The hydrogen desorption behavior has been correlated with the surface structure which appears to depend on the carbon to benzene ratio. Thermal stability and hydrogen desorption properties were investigated by DSC. Experimental results on nanocomposites with the same Mg to C weight ratio (70:30) show improved performances for a proper choice of carbon to benzene ratio weight (1/3), even after manipulation of the milled material in air.