This work considers the Dynamic Problem of Locating and Dispatching Emergency Medical Vehicles (PDLDVE). The problem considers three decisions sequentially: location of the fleet of emergency vehicles, the assigning and dispatching of the available vehicles, and finally the relocation of available vehicles, by considering a heterogeneous fleet of vehicles. The objective of the PDLDVE is to maximize coverage in terms of time of response depending on the type of service requested. In this work, a matheuristic algorithm is proposed addressing the three problems: location, dispatch and relocation. The problem of location is mathematically formulated with a vertex approach which is oriented towards the maximum coverage; the dispatch problem is solved through a heuristic based on the preparedness index for multiple servers; and, finally, the relocation problem is approached in two stages: in the first stage, a mathematical model related to maximum coverage is solved, and the second stage minimizes the maximum time need for the displacement of the vehicles in order to relocate the available fleet. Computational experiments generated in a simulation of discrete events based on real information for the city of Bogotá, Colombia, show that the proposed algorithm is able to obtain good solutions within short computing times.