Invasive species are a growing threat to food biosecurity and cause significant economic losses in agricultural systems. Despite their damaging effect, they are attractive models for the study of evolution and adaptation in newly colonised environments. The Mediterranean fruit fly, Ceratitis capitata, as a member of the family Tephritidae, is one of the most studied invasive species feeding on many fruit crops in the tropics and subtropics worldwide. This study aims to determine the global macrogeographic population structure of Ceratitis capitata and reconstruct its potential migration routes. A partial mitochondrial cytochrome oxidase I gene from >400 individual medflies and 14 populations from four continents was sequenced and subjected to Bayesian demographic modelling. The Afrotropical populations (Kenya, South Africa and Ghana) harbour the majority of haplotypes detected, which also are highly divergent, in accordance with the presumed ancestral range of medflies in Sub-Saharan Africa. All other populations in the presumed non-native areas were dominated by a single haplotype also present in South Africa, in addition to a few, closely related haplotypes unique to a single local population or regional set, but missing from Africa. Bayesian coalescence methods revealed recent migration pathways from Africa to all continents, in addition to limited bidirectional migration among many local and intercontinental routes. The detailed investigation of the recent migration history highlights the interconnectedness of affected crop production regions worldwide and pinpoints the routes and potential source areas requiring more specific quarantine measures.