The emergency medical services (EMS) provide the preliminary assistance and transportation for patients in need of urgent medical care in order to decrease the mortality rate and reduce the non-reversible effects of injuries. Since the objective is directly related to the human life, the value of the proposed solutions in order to improve the performance of EMS is highly welcomed. Mainly, there are three problems that EMS managers face with: location, allocation and redeployment of the EMS facilities/vehicles. Most of the studies in EMS literature focus on accurately modeling the probabilistic nature of the availability of an ambulance when it is called for. However, trivial changes in model parameters or estimates could dramatically change the optimal allocations generated by the probabilistic models and hence make the model invalid. In this study, we formulate the ambulance location problem as a deterministic multi-level maximal coverage model by which the total demand is tried to be covered as many as possible at multiple levels. Both a mathematical programming model and genetic algorithm-based heuristic approaches are proposed for the problem. The results indicate that the genetic algorithm-based solutions give reliable (near-optimal) and robust results in reasonable computational times for the problem. Moreover, the tradeoffs between the two performance measures, &lsquo / responsiveness&rsquo / and &lsquo / preparedness&rsquo / , are searched for / and our approaches with multi-level coverage are compared against the multiple coverage approaches in terms of these performance measures.