How communities of natural enemies, such as parasitoids, adapt to the range expansion of their hosts or the arrival of a novel invasive host is an important question in invasion biology. Do parasitoids track the expansion of their hosts from their shared native range? Do they locally adapt both behaviorally and physiologically to the arrival of a novel species by shifting hosts? Few studies have addressed those questions, yet they are important to develop efficient methods to manage invasive species. Here we focus on Pnigalio mediterraneus Ferriére and Delucchi (Hymenoptera: Eulophidae), an important parasitoid of two major agricultural and ornamental pests, the olive fruit fly Bactrocera oleae Rossi (Diptera: Tephritidae) and the horse chestnut leafminer Cameraria ohridella Deschka & Dimic (Lepidoptera: Gracillariidae). C. ohridella recently invaded Europe starting from the Southern Balkans, whereas B. oleae has been associated since the Quaternary with wild olives in the Mediterranean, where it largely spread after the domestication of cultivated olives. We used two markers, the ribosomal spacer ITS2 and the mitochondrial gene COI. Although the ITS2 dataset provided little variation and no phylogeographic signal, analysis of mtDNA of 188 individuals of P. mediterraneus from 54 European localities allowed us to identify 53 haplotypes. Both nucleotide and haplotype diversity were higher for Mediterranean samples, and from samples reared from B. oleae. The statistical parsimony network identified one haplotype as the most frequent, ancestral and mainly associated with C. ohridella. Our findings suggest that P. mediterraneus locally host switched to C. ohridella from other hosts in the Balkans and later tracked the horse chestnut leafminer invasion over Europe. Therefore both host-tracking and ecological sorting could explain the current distribution of P. mediterraneus haplotypes.