Here, we demonstrate a dioxolane (DOL)-based electrolyte with dimethyl sulfoxide (DMSO) as the low-temperature additive, which helps to construct a robust SEI layer that possesses uniform structure and good composition consistency even under extremely cold condition. In this electrolyte, DOL works as the primary electrolyte component that defines the basic electrochemical properties, while DMSO further tunes the SEI composition to boost the low-temperature performance. To elucidate the modified microstructure and chemical composition of the SEI film, cryogenic transmission electron microscopy, X-ray photoelectron spectroscopy, and energy-dispersive X-ray spectroscopy are conducted to make a comprehensive investigation. Moreover, a series of electrochemical tests are conducted under extremely cold environments, and results demonstrate that the adjusted SEI is resilient to the stripping and plating cycles of Li metal at temperatures as low as -80 °C. Full cells with lithium iron phosphate as the cathode material are assembled and good electrochemical performance is achieved at -40 °C at 0.2 C. The solvation structure of DMSO added electrolyte is also investigated to fundamentally understand how it affects the SEI formation. Our work establishes fundamental insights into the low-temperature electrolyte additives and paves the road to the further applications of LMBs in harsh environments.