Most invasive species established in Europe originate from either Asia or North America, but little is currently known about the potential of the Anatolian Peninsula (Asia Minor) and/or the Near East to constitute invasion sources. Mediterranean forests are generally fragile ecosystems that can be threatened by invasive organisms coming from different regions of the Mediterranean Basin, but for which historical data are difficult to gather and the phylogeographic patterns are still poorly understood for most terrestrial organisms. In this study, we characterized the genetic structure of Megastigmus schimitscheki, an invasive seed-feeding insect species originating from the Near East, and elucidated its invasion route in South-eastern France in the mid 1990s. To disentangle the evolutionary history of this introduction, we gathered samples from the main native regions (Taurus Mountains in Turkey, Lebanon and Cyprus) and from the invaded region that we genotyped using five microsatellite markers and for which we sequenced the mitochondrial Cytochrome Oxidase I gene. We applied a set of population genetic statistics and methods, including approximate Bayesian computation. We proposed a detailed phylogeographic pattern for the Near East populations, and we unambiguously showed that the French invasive populations originated from Cyprus, although the available historical data strongly suggested that Turkey could be the most plausible source area. Interestingly, we could show that the introduced populations were founded from an extremely restricted number of individuals that realized a host switch from Cedrus brevifolia to C. atlantica. Evolutionary hypotheses are discussed to account for this unlikely scenario.