Abstract Energy storage systems have been recently recognized as an effective solution to tackle power imbalances and voltage violations faced by distribution system operators due to the increasing penetration of low carbon technologies. To fully exploit their benefits, optimal sizing of these devices is a key problem at the planning stage. This paper considers the sizing problem of the energy storage systems installed in a distribution network with the aim, e.g., of preventing over- and undervoltages. In order to accommodate uncertainty on future realizations of demand and generation, the optimal sizing problem is formulated in a two-stage stochastic framework, where the first stage decision involves the storage sizes, while the second stage problem provides the optimal storage control policy for given demand and generation profiles. By taking a scenario-based approach, the two-stage problem is approximated in the form of a single multi-scenario, multi-period optimal power flow, whose size, however, becomes computationally intractable as the number of scenarios grows. To overcome this issue, the paper presents a procedure to compute upper- and lower bounds to the optimal cost of the approximate problem. Moreover, when the objective is to minimize the total installed storage capacity, an iterative algorithm based on scenario reduction is proposed, which converges to the optimal solution of the approximate problem. The whole procedure is tested on the topology of the IEEE 37-bus test network, considering scenarios of demand and generation which feature over- and undervoltages in the absence of storage devices.