We show how electricity storage is operated optimally when the load net of renewable output is uncertain. We estimate a diurnal Markov-process representation of how Germany's residual load changed from hour to hour and design a simple dynamic stochastic electricity system model with non-intermittent generation technologies and storage. We derive the optimal storage, generator output and capacity levels. If storage capacity replaces some generation capacity, the optimal storage strategy must balance arbitrage (between periods of high and low marginal cost) against precautionary storage to ensure energy is available throughout a long peak in net demand. Solving the model numerically under uncertainty (only the transition probabilities to future loads are known), we compare the results to perfect foresight findings. The latter over-estimate the cost-saving potential of energy storage by 27%, as storage can take up arbitrage opportunities that would not be chosen if there was a need for precautionary storage.