We propose a new stochastic modeling approach for a pre-disaster relief network design problem under uncertain demand and transportation capacities. We determine the size and the location of the response facilities and the inventory levels of relief supplies at each facility with the goal of guaranteeing a certain level of network reliability. The overall objective is to enhance the effectiveness of the post-disaster relief operations. We introduce a probabilistic constraint on the existence of a feasible flow to ensure that the demand for relief supplies across the network is satisfied with a specified high probability. The responsiveness criterion is accounted for by defining multiple regions in the network, and introducing a local probabilistic constraint on satisfying the demand within each region. These local constraints ensure that each region is self-sufficient in terms of providing for their own relief needs with a large probability. The Gale-Hoffman inequalities and a combinatorial method are used to reformulate the probabilistically constrained models as computationally efficient mixed-integer linear programs. The solution method enables the use of a large number of scenarios to model the dependency between uncertain variables affecting disaster relief networks. Computational results for a case study and randomly generated problem instances based on a real disaster network demonstrate the effectiveness of the models and solution methods.