Rechargeable lithium, sodium and aluminium metal-based batteries are among the most versatile platforms for high-energy, cost-effective electrochemical energy storage. Non-uniform metal deposition and dendrite formation on the negative electrode during repeated cycles of charge and discharge are major hurdles to commercialization of energy-storage devices based on each of these chemistries. A long-held view is that unstable electrodeposition is a consequence of inherent characteristics of these metals and their inability to form uniform electrodeposits on surfaces with inevitable defects. We report on electrodeposition of lithium in simple liquid electrolytes and in nanoporous solids infused with liquid electrolytes. We find that simple liquid electrolytes reinforced with halogenated salt blends exhibit stable long-term cycling at room temperature, often with no signs of deposition instabilities over hundreds of cycles of charge and discharge and thousands of operating hours. We rationalize these observations with the help of surface energy data for the electrolyte/lithium interface and impedance analysis of the interface during different stages of cell operation. Our findings provide support for an important recent theoretical prediction that the surface mobility of lithium is significantly enhanced in the presence of lithium halide salts. Our results also show that a high electrolyte modulus is unnecessary for stable electrodeposition of lithium.