The evolutionary history of the olive fly, Bactrocera oleae, was reconstructed in a phylogenetic and coalescent framework using full mitochondrial genome data from 21 individuals covering the entire worldwide distribution of the species. Special attention was given to reconstructing the timing of the processes under study. The early subdivision of the olive fly reflects the Quaternary differentiation between Olea europea subsp. europea in the Mediterranean area and the two lineages of Olea europea subsp. cuspidata in Africa and Asia, pointing to an early and close association between the olive fly and its host. The geographic structure and timing of olive fly differentiation in the Mediterranean indicates a clear connection with the post-glacial recolonization of wild olives in the area, and is irreconcilable with the early historical process of domestication and spread of the cultivated olive from its Levantine origin. Therefore, we suggest an early co-history of the olive fly with its wild host during the Quaternary and post-glacial periods and a multi-regional shift of olive flies to cultivated olives as these cultivars gradually replaced wild olives in historical times.