Emergency Medical Services (EMSs) provide necessary urgent medical care and transport patients to the nearest medical center for treatment. Due the to nature of the service, response time is of utmost importance for reducing mortality and alleviating human suffering. Moreover, the availability of service at the time of the call is another planning factor that should be considered. In fatal traffic accidents, for instance, the probability of death increases dramatically as a function of response time. Therefore, locating EMS stations and allocating ambulances to emergency calls requires careful and analytical planning. In this study, we aim to determine the locations and sizes of EMS stations in Istanbul. We formulate a multi-objective integer programming model that finds optimal locations of service stations and the number of ambulances to be stationed while satisfying response time and availability constraints. Our model also addresses allocation decisions where each demand point (subdistrict) is allocated to an EMS station that will ensure predetermined service levels in terms of response time and availability. In order to determine the number of ambulances to be located at a station, historical EMS calls are analyzed. To ensure a particular level of availability, the problem is formulated as a Q-coverage problem where the total number of ambulances to be stationed at an EMS station is driven by the demand (EMS calls) of subdistricts that are covered. The objectives of the model are to minimize the total cost of opening EMS stations and to minimize the total demand weighted distance of subdistricts to EMS stations. We solve the problem for the Anatolian side of Istanbul.