Lithium-ion rechargeable batteries have been demonstrated to have high energy density, high voltage, and excellent cycle life which make this technology more attractive than competing systems such as Ni-Cd and Ni-H2. However, the SOA cells fail to meet certain requirements necessary for various future NASA missions, such as good low temperature performance. Under a program sponsored by the Mars Exploration Program we have developed an organic non-aqueous electrolyte which has been demonstrated to result in improved low temperature performance of lithium-ion cells. The electrolyte formulation which has resulted in excellent low temperature performance, as well as good cycle life performance at both ambient and low temperatures, consists of a 1.0M solution of a lithium salt, lithium hexafluoro-phosphate (LiPF6), dissolved in a mixture of carbonates: ethylene carbonate + dimethyl carbonate + diethyl carbonate (1:1:1). Prototype cells with the improved electrolyte showed high capacity at low temperature (-20° to -40°C), high rate capabilities, and good cycle life at low temperature. These improvements were achieved through advances in materials development and cell design concepts.