This paper considers the design of a distribution network composed of a single supplier serving a set of retailers through a set of Distribution Centres (DCs) to locate. The number and location of DCs are decision variables and they are chosen from the set of retailer locations. Each retailer faces a random demand and the supplier lead-time is constant. Furthermore, some parameters are random and described by scenarios, each with a specified probability of occurrence. The problem is formulated as a two-stage non-linear discrete stochastic optimisation problem. At the first stage, we decide on the DCs location and at the second stage, we assign retailers to located DCs with respect to a given scenario. The goal is to minimise the expected total cost resulted from the DCs location, transportation, working inventory and safety stocks costs. A Lagrangian relaxation based approach is proposed to generate efficient solutions. Computational results are presented and analysed showing the effectiveness of the proposed approach.