Ever-growing energy needs and depleting fossil-fuel resources demand the pursuit of sustainable energy alternatives, including both renewable energy sources and sustainable storage technologies. It is therefore essential to incorporate material abundance, eco-efficient synthetic processes and life-cycle analysis into the design of new electrochemical storage systems. At present, a few existing technologies address these issues, but in each case, fundamental and technological hurdles remain to be overcome. Here we provide an overview of the current state of energy storage from a sustainability perspective. We introduce the notion of sustainability through discussion of the energy and environmental costs of state-of-the-art lithium-ion batteries, considering elemental abundance, toxicity, synthetic methods and scalability. With the same themes in mind, we also highlight current and future electrochemical storage systems beyond lithium-ion batteries. The complexity and importance of recycling battery materials is also discussed.