The focus of this study is on determining the change in capacity requirements and desirable shelter locations as a result of link capacity changes during evacuation. A cell transmission-based system optimal dynamic traffic assignment (SO-DTA) formulation first proposed by Ziliaskopoulos is extended by introducing probabilistic capacity constraints. The p-level efficient points method first proposed by Prékopa is used to deal with probabilistic capacity constraints of the proposed stochastic SO-DTA model. The model captures the probabilistic nature of link capacities that change in response to the impacts of events such as hurricanes and earthquakes that can destroy or damage highway links. First, a simple single-destination example network is studied to show the effectiveness of the proposed model. Then the impact of using stochastic and deterministic link capacities is also analyzed with a simplified multiple-origin, multiple-destination version of the Cape May, New Jersey, network. Desirable shelter locations are evaluated by letting the stochastic SO-DTA model assign flows generating the minimum systemwide travel time. The results indicate that introducing probabilistic link capacities can adjust the overall flow in the network as well as shelter utilization. Thus, if planners consider the predictions of the deterministic model, they may face the risk of not having sufficient food, medicine, and other emergency supplies in shelters. This paper suggests a more realistic approach to evacuation planning to avoid the inefficiencies that created problems after such recent major disasters as Hurricane Katrina and the tsunami in Southeast Asia.