Optimal deployment of limited emergency resources in a large area is of interest to public agencies at all levels. In this paper, the problem of allocating limited emergency service vehicles including fire engines, fire trucks, and ambulances among a set of candidate stations is formulated as a mixed integer linear programming model, in which the objective is to maximize the service coverage of critical transportation infrastructure (CTI). On the basis of this model, the effects of demand at CTI nodes and of transportation network performance on the optimal coverage of CTI are studied. In addition, given a fixed total budget, the most efficient distribution of investment among the three types of emergency service vehicles is identified. To cope with the uncertainty involved in some of the model parameters such as traffic network performance, formulations based on various risk preferences are proposed. The concept of regret is applied to evaluate the robustness of proposed resource allocation strategies. The applicability of the proposed methodologies to high-density metropolitan areas is demonstrated through a case study that uses data from current practice in Singapore.