Here we report for the first time the development of a Mg rechargeable battery using a graphene–sulfur nanocomposite as the cathode, a Mg–carbon composite as the anode and a non-nucleophilic Mg based complex in tetraglyme solvent as the electrolyte. The graphene–sulfur nanocomposites are prepared through a new pathway by the combination of thermal and chemical precipitation methods. The Mg/S cell delivers a higher reversible capacity (448 mA h g−1), a longer cyclability (236 mA h g−1 at the end of the 50th cycle) and a better rate capability than previously described cells. The dissolution of Mg polysulfides to the anode side was studied by X-ray photoelectron spectroscopy. The use of a graphene–sulfur composite cathode electrode, with the properties of a high surface area, a porous morphology, a very good electronic conductivity and the presence of oxygen functional groups, along with a non-nucleophilic Mg electrolyte gives an improved battery performance.