We introduce two statistical methods for estimating vehicle travel time distributions on a road network, using Global Positioning System (GPS) data recorded during historical vehicle trips. In the first method, we use a model of the path taken by each vehicle in the data, the travel time on each road segment in the network, and the location and speed errors for each GPS observation. In the second method, we use a model of the entire travel time of each trip, and include covariates such as the types of roads traveled and time of day. We estimate the parameters of both models by Markov chain Monte Carlo methods. We compare the performance of these methods with two simpler methods, a recently published method, and commercially available travel time estimates, using data from ambulance trips in Toronto and simulated data. Our methods outperform the alternative methods in point and distribution estimation of outof-sample trip travel times. Our methods also provide more realistic estimates than the recently published method of the probability that an ambulance is able to respond to each intersection in Toronto within a time threshold. We also consider map-matching, i.e. estimating a vehicle's path from sparse and error-prone GPS data, which is an important sub-problem for travel time estimation. In practice, successive GPS location readings are frequently biased in the same direction. We introduce a statistical map-matching method that takes into account bias in GPS locations, leading to improved accuracy.