Genetic diversity and spatial structure of populations are important for antagonistic coevolution. We investigated genetic variation and population structure of three closely related European ant species: the social parasite Harpagoxenus sublaevis and its two host species Leptothorax acervorum and Leptothorax muscorum. We sampled populations in 12 countries and analyzed eight microsatellite loci and an mtDNA sequence. We found high levels of genetic variation in all three species, only slightly less variation in the host L. muscorum. Using a newly introduced measure of differentiation (Jost's DEST), we detected strong population structuring in all species and less male-biased dispersal than previously thought. We found no phylogeographic patterns that could give information on post-glacial colonization routes - northern populations are as variable as more southern populations. We conclude that conditions for Thompson's geographic mosaic of coevolution are ideal in this system: all three species show ample genetic variation and strong population structure.