Based on previous data and an understanding of possible reactions with electrodes, we selected five electrolyte solutions as promising components for Li-ion batteries that can operate down to -40 degrees C, consisting of solutions of LiPF6 or LiTFSI electrolytes in optimized ternary carbonate solvent mixtures and quaternary solvent mixtures containing esters, both with and without vinylene carbonate and LiBOB salt as additives. The main criteria for selecting these solutions were a specific conductivity >= 1 mS/cm at -40 degrees C and the ability to work well with a wide variety of electrode materials (for example, transition metal oxides and phosphoolivine cathodes, lithiated titanium oxide and carbon anodes) over a temperature range of -40 to +60 degrees C. As a first step in the selection of battery materials for operation at low temperatures, we focused our work on the negative electrodes and tested three types of graphite electrodes with these electrolyte solutions. In general, practical graphite electrodes can work reasonably well only at temperatures above -20 degrees C. A limited improvement of their low temperature performance can be achieved by increasing the surface area (i.e., decreasing the particle size) of the active material at the expense of high initial irreversible capacity. (C) 2010 The Electrochemical Society. [DOI: 10.1149/1.3507259] All rights reserved.