Battery electrolytes are the medium that link the battery anode and the cathode. As such, they need to simultaneously satisfy a myriad of requirements that make the development of electrolytes a challenging endeavor. That is, at the very minimum, they need to possess a sufficient electrochemical stability window together with acceptable ionic transport. To become practical, other physical and chemical properties such as low volatility, non-flammability, inertness and high thermal stability are also desirable. The development of electrolytes for rechargeable magnesium batteries was previously challenged by the absence of practical electrolytes that are compatible with Mg metal. Over the past decade, rapid new developments have generated new ideas and designs that are altering the landscape of magnesium electrolytes. In this chapter, we discuss these new advancements and explain how they are changing our previous perceived image of a competent Mg electrolyte.