The co-evolution between hosts and parasites has long been recognized as a fundamental driver of macro-evolutionary patterns of diversification. The effect of co-differentiation on parasite diversification is, however, often confounded by underlying geographic patterns of host distribution. In order to disentangle the confounding effects of allopatric versus host speciation, the mitochondrial cytochrome b (cyt b) gene was sequenced in seventy individuals of the parasitic nematode genus Heligmosomoides sampled in the six Apodemus mice species common in the western Palearctic region. The nuclear internal transcribed spacers (ITS) 1 and 2 were also sequenced in fifteen parasites to confirm the mitochondrial data. All lineages differentiated according to a geographic pattern and independently from the sampled host species. This suggests that host speciation did not involve concurrent parasite speciation. However, the geographic distribution range of some parasite lineages mirrors that of A. sylvaticus lineages in SW Europe, and that of A. flavicollis lineages in the Balkans and in the Middle East. Thus, regional co-differentiation likely occurred between the parasite and the two sister Apodemus hosts in different parts of their distribution range. We suggest that differences in regional abundances of A. sylvaticus and A. flavicollis are responsible for generating this pattern of regional co-differentiation. This study highlights the importance of integrating both geography and biogeographic information from potential hosts to better understand their parasite phylogeography.