Nonaqueous sodium-based batteries are ideal candidates for the next generation of electrochemical energy storage devices. However, despite the promising performance at ambient temperature, their low-temperature (e.g., < 0 °C) operation is detrimentally affected by the increase in the electrolyte resistance and solid electrolyte interphase (SEI) instability. Here, to circumvent these issues, we propose specific electrolyte formulations comprising linear and cyclic ether-based solvents and sodium trifluoromethanesulfonate salt that are thermally stable down to −150 °C and enable the formation of a stable SEI at low temperatures. When tested in the Na||Na coin cell configuration, the low-temperature electrolytes enable long-term cycling down to −80 °C. Via ex situ physicochemical (e.g., X-ray photoelectron spectroscopy, cryogenic transmission electron microscopy and atomic force microscopy) electrode measurements and density functional theory calculations, we investigate the mechanisms responsible for efficient low-temperature electrochemical performance. We also report the assembly and testing between −20 °C and −60 °C of full Na||Na₃V₂(PO₄)₃ coin cells. The cell tested at −40 °C shows an initial discharge capacity of 68 mAh g⁻¹ with a capacity retention of approximately 94% after 100 cycles at 22 mA g⁻¹.