Emergency medical systems are an essential part of the modern healthcare system, and systematic decision-making is essential to respond quickly to emergency medical services. This paper discusses the issue of deploying and relocating ambulances at a strategic and tactical level to improve the arrival rate of ambulances within golden time after an emergency. To this end, we propose integer programming formulations that determine the relocation of existing ambulances and the deployment of new ambulances simultaneously to minimize ambulance travel distance. Our case study is conducted on real-world instances from three regions of Gyeongsangnam-do, Korea. The results of the case study show that the solutions obtained from our models can reduce the distance traveled by ambulances, and therefore can be used effectively to develop plans for the deployment and relocation of ambulances in practice.