In an emergency medical service (EMS) system, the depot location and fleet assignment greatly affect the average response time, which is the main criterion for measuring system performance. Whereas the EMS depot location problem is a strategic problem, the fleet assignment problem is a tactical one. As such, the EMS depot location and fleet assignment problems are usually solved separately under some simplified assumptions. However, there is a potential for savings in both the average response times and the capital and operating costs if these problems can be solved simultaneously. A simulation model for EMS vehicle dispatching was developed. This model is calibrated with real-world data, and it is incorporated in a genetic algorithm to help solve the EMS depot location and fleet assignment problems simultaneously. Emergency types, their response priorities, and whether or not they require dispatching of multiple units are taken into consideration in the model. The average response time and the capital and operating costs are used as criteria for evaluation.