Comparative studies of genetic diversity and population structure can shed light on the ecological and evolutionary factors governing host–parasite interactions. Even though they are considered of major biological importance, little is known about the adaptation potential of invasive parasites in their new ranges. Here, the genetic diversification of Varroa destructor, a novel parasite of Apis mellifera originating from Asia, was investigated using population genetics to compare how the genetic structure of the parasite changed in response to its interactions with distinct European populations of its new host. To do so, mites infesting two categories of hosts in four European regions were compared: (i) adapted hosts surviving through means of natural selection, thereby expected to impose strong selective pressure on the mites, and (ii) susceptible host populations, surviving because acaricides are applied, therefore characterized by a relaxed selection imposed by the host. Significant genetic divergence was found across regions, reflecting partially the invasion pattern of V. destructor throughout Europe, but also local adaptation of the mite to the host populations. Additionally, varying degrees of genotypic changes were found between mites from adapted and susceptible colonies. Altogether, these results indicate that V. destructor managed to overcome the genetic bottlenecks following its introduction in Europe and that host-mediated selection fostered changes in the genetic structure of this mite at diverse geographical scales. These findings highlight the potential of parasites to adapt to their local host populations and confirm that adaptations developed within co-evolutionary dynamics are a major determinant of population genetic changes.