Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a stochastic version where operational costs are uncertain because of fluctuating demand and estimated as a sample average from historical data. This problem is computationally challenging, and instances with as few as 100 nodes often cannot be solved to optimality using current decomposition techniques. We propose a stochastic variant of Benders decomposition that mitigates the high computational cost of generating each cut by sampling a subset of the data at each iteration and nonetheless, generates deterministically valid cuts, via a dual averaging technique, rather than the probabilistically valid cuts frequently proposed in the stochastic optimization literature. We implement both single-cut and multicut variants of this Benders decomposition as well as a variant that uses clustering of the historical scenarios. To our knowledge, this is the first single-tree implementation of Benders decomposition that facilitates sampling. On instances with 100–200 nodes and relatively complete recourse, our algorithm achieves 5%–7% optimality gaps compared with 16%–27% for deterministic Benders schemes, and it scales to instances with 700 nodes and 50 commodities within hours. Beyond network design, our strategy could be adapted to generic two-stage stochastic mixed-integer optimization problems where second-stage costs are estimated via a sample average.