One of the major challenges that has limited the success of magnesium-ion based battery chemistries is the development of suitable electrolytes that enable the reversible deposition of magnesium metal with high coulombic efficiency, high conductivity, and practical oxidative stability on non-noble metal surfaces. With few exceptions, the tenacious oxide layer on magnesium metal has limited the scope of research to halide ion-based electrolytes, which help activate the electrode surface but also limit the working voltage window considerably and can cause pitting and corrosion to parts commonly used in coin cells. Here we discuss our efforts at developing new halide-free magnesium ion electrolytes based on fluoroalkoxyaluminate anions synthesized via a facile and scalable method and its incorporation in a full battery cell. Our results show a large voltage window on stainless steel and aluminum (4-5 V vs. Mg), high conductivity (comparable with lithium ion electrolytes), and near unity Coulombic efficiency. We will discuss characterization of the electrolyte, identity of solution species, and promising methods of modifying the electrolyte for improved figures of merit.