Predicting ambulance demand accurately on a fine resolution in time (e.g., every hour) and space (e.g., every 1 km2 ) is critical for staff, fleet management and dynamic deployment. There are several challenges: although the dataset is typically large-scale, the number of observations per time period and locality is almost always zero. The demand arises from complex urban geography and exhibits complex spatio-temporal patterns, both of which we need to capture and exploit. We propose three new methods to address these challenges, and provide spatio-temporal predictions for Toronto, Canada and Melbourne, Australia. First, we introduce a Bayesian time-varying Gaussian mixture model. We fix the mixture component distributions across time, while representing the spatiotemporal dynamics through time-varying mixture weights. We constrain the weights to capture weekly seasonality, and apply autoregressive priors on them to model location-specific patterns. Second, we propose a spatio-temporal kernel density estimator. We weight the spatial kernel of each historical observation by its informativeness to the current predictive task. We construct spatio-temporal weight functions to incorporate various temporal and spatial patterns in ambulance demand. Third, we propose a kernel warping method to incorporate complex spatial features. For each prediction we build a kernel density estimator on a sparse set of most similar data (labeled data), and warp these kernels to a larger set of past data regardless of labels (point cloud). The point cloud represents boundaries, neighborhoods, and road networks. Kernel warping can be interpreted as a regularization and a Bayesian prior imposed for spatial features. We show that these methods give much higher statistical predictive accuracy, and reduce error in predicting EMS operational performance by as much as two-thirds compared to the industry practice.