Every patient should have equal access to fast and qualified assistance by emergency medical services (EMS). Most location planning models for EMS only consider efficiency criteria such as maximum coverage. Especially in metropolitan regions, the heterogeneous distribution of demand leads to unequal service availability: city centers receive higher coverage than suburban areas. To address this issue, we extend existing location planning models by two fairness criteria: the Rawlsian criterion, which maximizes the coverage of the least-covered demand area, and the Gini coefficient, which minimizes differences in coverage between demand areas. We consider both fairness criteria using the ϵ-constraint method and apply both criteria to the case of a German EMS provider. By generating the Pareto front, we analyze the trade-offs between efficiency and fairness. We find that managing the conflict between fairness and efficiency especially in a metropolitan region offers more beneficial solutions with respect to both criteria than generally assumed. We show that it is possible to greatly improve fairness by giving up only a small amount of coverage.