This paper considers a dynamic Emergency Medical Services (EMS) network design problem and introduces two novel two-stage stochastic programming formulations that account for uncertainty about emergency demand. Similarly to some recent work on emergency demand coverage, we consider both a constraint on the probability of covering the realized emergency demand and minimize the expected cost of doing so, yet unlike other formulations, our optimization models account for the dynamics throughout a full day of operations and allow the EMS system managers to control the degradation of coverage under the more severe scenarios. In order to do so, we present both a two-stage chance-constrained stochastic programming formulation and a variant of this model, which employs probabilistic envelope constraints. These give rise to large mixed-integer programs, which can be tackled directly or using a conservative approximation scheme. To improve the numerical efficiency of the exact approach, we implement the Branch-and-Benders-Cut method, which improves significantly the solution time when compared to a state-of-the art Branch-and-Bound algorithm proposed in the recent literature for a simplified version of these problems. Finally, a practical study is conducted using historical data from Northern Ireland Ambulance Service Health and Social Care Trust and sheds some light on optimal EMS network configuration for this region and necessary trade-offs that must be made between emergency demand coverage and expected cost. These insights are confirmed through an out-of-sample analysis.