Estimates of ambulance travel times on road networks are critical for effective ambulance base placement and real-time ambulance dispatching. We introduce new methods for estimating the distribution of travel times on each road segment in a city, using Global Positioning System (GPS) data recorded during ambulance trips. Our preferred method uses a Bayesian model of the ambulance trips and GPS data. Due to sparseness and error in the GPS data, the exact ambulance paths and travel times on each road segment are unknown. To estimate the travel time distributions using the GPS data, we must also estimate each ambulance path. This is called the map-matching problem. We consider the unknown paths and travel times to be missing data, and simultaneously estimate them and the parameters of each road segment travel time distribution using Bayesian data augmentation. We also introduce two alternative estimation methods using GPS speed data that are simple to implement in practice. We test the predictive accuracy of the three methods on a subregion of Toronto, using simulated data and data from Toronto EMS. All three methods perform well. Point estimates of ambulance trip durations from the Bayesian method outperform estimates from the alternative methods by roughly 5% in root mean squared error. Interval estimates from the Bayesian method for the Toronto EMS data are substantially better than interval estimates from the alternative methods. Map-matching estimates from the Bayesian method are robust to large GPS location errors, and interpolate well between widely spaced GPS points.