The risk of tsunami threatens the whole Caribbean coastline and especially the Lesser Antilles. The available models of tsunami propagation estimate that the travel time from the closest seismic sources would only take a few minutes to impact the Martinique Island. Considering this high threat, the most effective measure is a planned and organized evacuation of the coastal population. This requires an efficient regional warning system, estimation of the maximum expected tsunami flood height, preparation of the population to evacuate, and drawing up of local and regional emergency plans. In this context, this paper proposes a methodology directly addressed to decision makers in order to optimize and map the evacuation sites and route using a pedestrian accessibility modeling. It is based on a population database at a local scale, the development of connected graphs of roads, the identification of potential safe areas and the velocity setting for pedestrians. Evacuation routes are calculated using the Dijkstra’s algorithm which gives the fastest path between areas at risk and designated evacuation sites. A first application allows us to map the theoretical times to keep safe the exposed population and to compare these with a tsunami travel time scenario for each commune of Martinique. A second application results in a local evacuation plan for the commune of Saint-Anne. This new prevention support was validated by an expert committee and constitute the first mapping of this kind in France. This calibrated and officially approved methodology will be asked to be developed on other countries, but as a priority on overseas french departments.