Movements and spatial distribution of host populations are expected to shape the genetic structure of their parasite populations. Comparing the genetic patterns of both interacting species may improve our understanding of their evolutionary history. Moreover, genetic analyses of parasites with horizontal transmission may serve as indicators of historical events or current demographic processes that are not apparent in the genetic signature of their hosts. Here, we compared mitochondrial variation in populations of the ectoparasitic mite Spinturnix myoti with the genetic pattern of its host, the Maghrebian bat Myotis punicus in North Africa and in the islands of Corsica and Sardinia. Mite mitochondrial differentiation among populations was correlated with both host mitochondrial and nuclear differentiation, suggesting spatial co-differentiation of the lineages of the two interacting species. Therefore our results suggest that parasite dispersal is exclusively mediated by host movements, with open water between landmasses as a main barrier for host and parasite dispersal. Surprisingly the unique presence of a continental European mite lineage in Corsica was inconsistent with host phylogeographical history and strongly suggests the former presence of European mouse-eared bats on this island. Parasites may thus act as biological tags to reveal the presence of their now locally extinct host.