Due to global environmental concerns, our electricity supply will transform from mostly conventional power generation to mostly fluctuating renewable power generation. The transition will require combined backup from conventional sources and storage. A phase transition emerges during the ramp-up of the required amount of storage, with renewable penetration being the control parameter and average relative storage filling level being the order parameter. A singularity appears for the required storage energy capacity at a renewable penetration determined by the parameters of the storage. For an ideal storage with no roundtrip losses the transition occurs at 100% renewable penetration. Moreover, the required storage energy capacity is strongly enhanced by temporal correlations on the synoptic weather time scale. A Markov process is proposed, which reproduces these findings.