The location of ambulances is a crucial strategic decision for Emergency Medical Services (EMS). The base stations must achieve efficient dispatching under the inherent uncertainty of emergency locations and travel times. Additionally, managers need decision-support models that incorporate the multi-objective nature of such an efficient system. This paper bridges the gap between these requirements by developing a multi-objective hierarchical compromise optimization framework under stochastic travel times. Our hierarchical compromise optimization approach leverages quasi-optimal coverage solutions to provide EMS managers with flexibility in balancing (a) minimal average response time, (b) maximal resource adequacy, and (c) minimal worst-case response times. The stochasticity of travel times is incorporated into the models using a methodology to estimate continuous probability distributions for available and non-available historical data. The proposed modeling induces cross-scenario constraints, which are computationally challenging as the problem size increases. We tackle this issue by presenting an ad-hoc extension of a primal scenario-decomposition algorithm that deals with such constraints. This extension achieves superior performance over state-of-the-art optimization software. Finally, we use real-world data from the Basque Public Healthcare System to test the framework and prove the managerial interest of the obtained results.