A number of recent techno-economic studies have shown that energy storage could offer significant benefits to a low-carbon UK energy system as it faces increased challenges in matching supply and demand. However, the majority of this work has not investigated the real-world issues affecting the widespread deployment of storage. This paper is designed to address this gap by drawing on the systems innovation and socio-technical transitions literature to identify some of the most important contextual factors which are likely to influence storage deployment. Specifically it uses a coevolutionary framework to examine how changes in ecosystems, user practices, business strategies, institutions and technologies are creating a new selection environment and potentially opening up the energy system to new variations of storage for both electricity and heat. The analysis shows how these different dimensions of the energy regime can coevolve in mutually reinforcing ways to create alternative pathways for the energy system which in turn have different flexibility requirements and imply different roles for storage technologies. Using this framework three pathways are developed - user led, decentralised and centralised - which illustrate potential long-term trajectories for energy storage technologies in a low-carbon energy system.