Magnesium-ion batteries are one of the most researched multivalent-ion chemistries because of the ability to use energy-dense metallic magnesium anodes, which have a higher volumetric energy density compared to metallic lithium. One of the key limiting factors in bringing these batteries to fruition has been 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 and calcium-ion electrolytes based on fluoroalkoxyaluminate anions synthesized via a facile and scalable method. Our results for Mg 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. Using a combination of x-ray photoelectron spectroscopy and energy-dispersive x-ray spectroscopy, we analyze how electrolyte composition affects surface structures and elemental makeup of both the magnesium anode and deposits on the counterelectrode over multiple plating/stripping cycles. Flourinated alkoxyaluminate electrolytes represent a new class of halide free chemistries with the potential to significantly enhance performance in multivalent energy storage systems.