The first working Mg rechargeable battery prototypes were ready for presentation about 13 years ago after two breakthroughs. The first was the development of non-Grignard Mg complex electrolyte solutions with reasonably wide electrochemical windows in which Mg electrodes are fully reversible. The second breakthrough was attained by demonstrating high-rate Mg cathodes based on Chevrel phases. These prototypes could compete with lead–acid or Ni–Cd batteries in terms of energy density, very low self-discharge, a wide temperature range of operation, and an impressive prolonged cycle life. However, the energy density and rate capability of these Mg battery prototypes were not attractive enough to commercialize them. Since then we have seen gradual progress in the development of better electrolyte solutions, as well as suggestions of new cathodes. In this article we review the recent accumulated experience, understandings, new strategies and materials, in the continuous R&D process of non-aqueous Mg batteries. This paper provides a road-map of this field during the last decade.