Foot-and-mouth disease (FMD) affects the livestock industry and socioeconomic sustainability of many African countries. The success of FMD control programs in Africa depends largely on understanding the dynamics of FMD virus (FMDV) spread. In light of the recent outbreaks of FMD that affected the North-Western African countries in 2018 and 2019, we investigated the evolutionary phylodynamics of the causative serotype O viral strains all belonging to the East-Africa 3 topotype (O/EA-3). We analyzed a total of 489 sequences encoding the FMDV VP1 genome region generated from samples collected from 25 African and Western Asian countries between 1974 and 2019. Using Bayesian evolutionary models on genomic and epidemiological data, we inferred the routes of introduction and migration of the FMDV O/EA-3 topotype at the inter-regional scale. We inferred a mean substitution rate of 6.64 × 10  nt/site/year and we predicted that the most recent common ancestor for our panel of samples circulated between February 1967 and November 1973 in Yemen, likely reflecting the epidemiological situation in under sampled cattle-exporting East African countries. Our study also reinforces the role previously described of Sudan and South Sudan as a frequent source of FMDVs spread. In particular, we identified two transboundary routes of O/EA-3 diffusion: the first from Sudan to North-East Africa, and from the latter into Israel and Palestine AT; a second from Sudan to Nigeria, Cameroon, and from there to further into West and North-West Africa. This study highlights the necessity to reinforce surveillance at an inter-regional scale in Africa and Western Asia, in particular along the identified migration routes for the implementation of efficient control measures in the fight against FMD.