To ensure a timely response to emergencies, govements are obliged to implement effective ambulance allocation plans. In practice, an emergency medical service (EMS) system works in an uncertain environment, with stochastic demand, response-times, and travel-times. This uncertainty significantly affects ambulance allocation planning. How-ever, few studies in this field adequately consider the effect of spatiotemporal uncertainty in demand, because it is difficult to measure it quantitatively. As a result, few analytic models capture the dynamic nature of an EMS system and, thus, the allocation plans they generate are not efficient in practice. Therefore, this study proposes a simulation-based optimization method for ambulance allocation. A simulation model is constructed to mimic the operational processes of an EMS system, and to evaluate the performance of an ambulance allocation plan in an uncertain environment. Gaussian mixture model clus-tering is used to derive the uncertain spatial demand. Then, the simulation generates emergency demand based on the obtained spatial distribution. A Gaussian-process-based search algorithm is used together with the simulation model to identify optimal solutions. To validate the proposed method, a case study is conducted using data on emergency patients in the Shanghai Songjiang District. Compared with the current plan adopted in Songjiang, the experimental results demonstrate that the delay time and frequency of the EMS system can be reduced significantly by employing the proposed methods. Further-more, nearly 41% of the allocation cost can be saved.