Lithium metal and alloy anodes offer the promise of improved capacity for Li-based batteries, and they could overcome low-temperature diffusion limitations associated with graphite. However, the electrochemical behavior of these materials at low temperatures has been seldom investigated, and most liquid electrolytes exhibit extremely low Coulombic efficiency (CE) for cycling of these high-capacity electrode materials at low temperatures. Here, we demonstrate an ether-based electrolyte system with carbonate additives that substantially improves the CE of lithium metal cycling down to -60 °C. Lithium metal deposited at low temperatures in this and other electrolytes shows a clear reduction in grain size with decreasing temperature, which is correlated with lower CE. Cryo-TEM and X-ray photoelectron spectroscopy investigation of the solid-electrolyte interphase (SEI) shows that this tailored electrolyte allows for greater inorganic content in the SEI at low temperatures, which enables a compact and conducting passivation layer. We further extend these studies to sodium metal anodes, which show improved CE at low temperatures compared to lithium. Finally, we investigate alloy anode materials and show that they can exhibit stable electrochemical cycling down to -40 °C, indicating the promise of these high-capacity materials for low-temperature batteries.