Sulfolane (tetramethylene sulfone, SL) is known for leading to Li-ion electrolytes with high anodic stability. However, the operation of graphite electrodes in alternative electrolytes is usually challenging, especially when ethylene carbonate (EC) is not used as co-solvent. Thus, we study here the influence of the lithium salt on the physico-chemical and electrochemical properties of EC-free SL-based electrolytes and on the performance of graphite electrodes based on carboxymethyl cellulose (CMC). SL mixed with dimethyl carbonate (DMC) leads to electrolytes as conductive as state-of-the-art alkyl carbonate-based electrolytes with wide electrochemical stability windows. The compatibility with graphite electrodes depends on the Li salt used and, even though cycling is possible with most salts, lithium difluoro-oxalato borate (LiDFOB) is especially interesting for graphite operation. LiDFOB electrolytes are conductive at room temperature (ca. 6 mS cm(-1)) with an anodic stability slightly below 5 V vs. Li/Li+ on particulate carbon black electrodes. In addition, it allows cycling graphite electrodes with steady capacity and high coulombic efficiency without any additive. The testing of graphite electrodes in half-cells is, however, problematic with SL:DMC mixtures and, by switching the Li metal counter electrode for LiFePO4, the graphite electrode achieves better practical performance in terms of rate capability.