This work proposes a framework to aid the strategic decision making regarding the proper location of fire stations as well as their assignment of vehicles to improve emergency response. We present an iterative simulation–optimization approach that based on some precomputed utilization parameters updates the optimal location of vehicles and fire stations. First, we find an optimal solution by using a robust formulation of the Facility Location and Equipment Emplacement Technique with Expected Coverage (Robust FLEET-EXC) model, which maximizes demand considering vehicles’ utilization. Second, we use this solution as an input to a discrete event simulation model to compute utilization parameters. Then, if the obtained parameters deviate less than a desired error, the solution is maintained; otherwise, a new solution is computed with these new parameters. Additionally, the emergencies arrival process is modeled by a spatio-temporal sampling method that loosely couples a Kernel Density Estimator and a non-homogeneous non-renewal arrival process with a Markov-Mixture of Erlangs of Common Order model as base process. Then, the proposed robust model is compared to a deterministic FLEET model that does not account for vehicles’ availability, and the FLEET-EXC model with simulated utilization parameters. The main results show that the proposed spatio-temporal sampling method achieves a better representation of the emergency arrival process than those generally used in literature, and the resulting utilization parameters are statistically different than those produced by a Hypercube Queueing Model. On the other hand, the simulation–optimization approach that uses the Robust FLEET-EXC has the best performance, achieving the highest coverage of emergencies in 13 out of 15 experiments. Finally, this model is statistically better than the deterministic FLEET in all but one experiment, resulting in up to 6.42% more coverage.