Rechargeable magnesium–sulfur (Mg-S) batteries are emerging as a promising candidate for next-generation energy storage technologies owing to their prominent advantages in terms of high volumetric energy density, low cost, and enhanced safety. However, their practical implementation is facing great challenges in finding electrolytes that can fulfill a multitude of rigorous requirements along with efficient sulfur cathodes and magnesium anodes. This review highlights electrolyte design for reliable Mg-S batteries in terms of efficient Mg-based salt construction (cation/anion design of organomagnesium salt-based electrolytes, optimization of all inorganic salt-based electrolytes and choosing of simple salt-based electrolytes), suitable solvent selection, and strategies for confronting corrosivity of Mg electrolytes. Before the comprehensive overview of the research status of Mg-based electrolytes, the understanding of Mg–S electrochemistry and views on the recent progress and potential strategies for high-performance S-based cathode and Mg anode are also provided for a holistic insight into Mg–S systems. At the end, the perspectives on the possible research directions for constructing high performance practical Mg–S batteries are also shared.