In highly urbanized area where traffic condition fluctuates constantly, transportation infrastructure is one of the major contributing factors to Emergency Medical Service (EMS) availability and patient outcome. In this paper, we assess the impact of traffic fluctuation to the EMS first response availability in urban area, by evaluating the k-minute coverage under 21 traffic scenarios. The set of traffic scenarios represents the time-of-day and day-of-week effects, and is generated by combining road link speed information from multiple historical speed databases. In addition to the k-minute area coverage calculation, the k-minute population coverage is also evaluated for every 100m by 100m grid that partitions the case study area of Seoul, South Korea. In the baseline case of traveling at the speed limit, both the area and population coverage reached nearly 100% when compared to the five-minute travel time national target. Employing the proposed LoST (Loss of Serviceability due to Traffic) index, which measures coverage reduction in percentage compared to the baseline case, we find that the citywide average LoST for area and population coverage are similar at 34.2% and 33.8%. However, district-wise analysis reveals that such reduction varies significantly by district, and the magnitude of area and population coverage reduction is not always proportional. We conclude that the effect of traffic variation is significant to successful urban EMS first response performance, and regional variation is evident among local districts. Complexity in the urban environment requires a more adaptive approach in public health resource management and EMS performance target determination.