Ambulance travel time estimations play a pivotal role in ensuring timely and efficient emergency medical care by predicting the duration for an ambulance to reach a specific location. Overlooking factors such as local traffic situations, day of the week, hour of the day, or the weather may create a risk of inaccurately estimating the ambulance travel times, which might lead to delayed emergency response times, potentially impacting patient outcomes. In the current paper, we propose a novel framework for accurately estimating ambulance travel times using machine learning paradigms, employing real-world spatiotemporal ambulance data from the Skane region, Sweden. Our framework includes data preprocessing and feature engineering, with a focus on variables significantly correlated with travel time. First, through a comprehensive exploratory data analysis, we highlight the main characteristics, patterns, and underlying trends of the considered ambulance data set. Then, we present an extensive empirical analysis comparing the performance of different machine learning models across different ambulance travel trip scenarios and feature sets, revealing insights into the importance of each feature in improving the estimation accuracy. Our experiments indicate that the aforementioned factors play a significant role when estimating the travel time.