The host-parasite genera Proformica-Rossomyrmex present four pairs of species with a very wide range of distribution from China to Southeastern Spain, from huge extended plains to the top of high mountains. Here we review (1) the published data on these pairs in comparison to other slave-makers; (2) the different dispersal ability in hosts and parasites inferred from genetics (chance of migration conditions the evolutionary potential of the species); (3) the evolutionary potential of host and parasite determining the coevolutionary process in each host-parasite system that we treat to define using cuticular chemical data. We find a lower evolutionary potential in parasites than in hosts in fragmented populations, where selective pressures give advantage to a limited female parasite migration due to uncertainty of locating a host nest. A similar evolutionary potential is detected for hosts and parasites when the finding of host nests is likely (i.e., in continuous and extended populations). Moreover, some level of local adaptation at CHC profiles between host and parasite exists independently of the kind of geographic distribution and the ability of dispersal of the different populations. Similarity at CHC profiles appears to be a trait imposed by natural selection for the interaction between hosts and slave-makers.