Embodiments of a non-aqueous electrolyte for a rechargeable sodium (Na)-based battery comprise a sodium salt and a nonaqueous solvent, the electrolyte having a sodium salt concentration ≧2.5 M or a solvent-sodium salt mole ratio ≦4:1. Na-based rechargeable batteries including the electrolyte exhibit both high cycling stability and high coulombic efficiency (CE). Some embodiments of the disclosed batteries attain a CE≧80% within 10-30 charge-discharge cycles and maintain a CE≧80% for at least 100 charge-discharge cycles. In certain embodiments, the battery is an anode-free battery in the as-assembled initial state.