This paper addresses the design of a distribution network in which a single supplier ships products to a set of retailers facing random demands via a set of distribution centers. Distribution centers are not known a priori and are to be located at a set of retailer locations. Decisions include: retailer locations to be selected as distribution centers, assignment of retailers to the distribution centers, and inventory to keep at each distribution center. The goal is to minimize the total location, shipment, and inventory costs, while ensuring a given retailer service level. A Lagrangian relaxation heuristic is proposed. Computation results show the effectiveness of the proposed heuristic and the duality gap is less than 1.5% in all tested problem instances.