This paper is concerned with extending models for the Maximal Covering Location Problem in two ways. First, the usual 0-1 coverage definition is replaced by the probability of covering a demand within the target time. Second, once the locations are determined, the minimum number of vehicles at each location that satisfies the required performance levels is determined. Thus, the problem of identifying the optimal locations of a pre-specified number of emergency medical service stations is addressed by goal programming. The first goal is to locate these stations so the maximum expected demand can be reached within a pre-specified target time. Then, the second goal is to ensure that any demand arising located within the service area of the station will find at least one vehicle, such as an ambulance, available. Erlangs loss formula is used to identify the arrival rates when it is necessary to add an ambulance in order to maintain the performance level for the availability of ambulances. The model developed has been used to evaluate locations for the Saudi Arabian Red Crescent Society, Riyadh City, Saudi Arabia.