Invasive species may change the life history strategies, distribution, genetic configuration and trophic interactions of native species. The diamondback moth, Plutella xylostella L., is an invasive herbivore attacking cultivated and wild brassica plants worldwide. Here we present phylogeographic analyses of P. xylostella and one of its major parasitoids, Cotesia vestalis, using mitochondrial markers, revealing the genetic diversity and evolutionary history of these two species. We find evidence that C. vestalis originated in Southwest China, then adapted to P. xylostella as a new host by ecological sorting as P. xylostella expanded its geographic range into this region. Associated with the expansion of P. xylostella, Wolbachia symbionts were introduced into local populations of the parasitoid through horizontal transfer from its newly associated host. Insights into the evolutionary history and phylogeographic system of the herbivore and its parasitoid provide an important basis for better understanding the impacts of biological invasion on genetic configuration of local species.