We analysed the phylogenetic and phylogeographic relationships of four Mediterranean species of the rare slave-making ant genus Chalepoxenus and eleven of its about 20 Temnothorax host species by sequencing the mitochondrial Cytochrome Oxidase I and II genes. Neighbour-Joining, Maximum Parsimony and Bayesian analyses based on 1320 bp indicate that the genus Chalepoxenus constitutes a monophylum. In all three analyses, C. kutteri from Southwest Europe and the workerless, "degenerate slavemaker" C. brunneus from North Africa form a monophyletic group. C. muellerianus and C. tauricus, distributed in Southern Europe and Ukraine, respectively, form a monophylum in the Neighbour-Joining and the Maximum Parsimony analysis. In our limited set of only 11 of several hundred Temnothorax species, T. flavicornis forms the sister group of Chalepoxenus. Our study further indicates paraphyly of the genus Temnothorax with respect to Chalepoxenus. Moreover, the results suggest that speciation in this slave-making genus is possibly caused by the formation of host races as different Chalepoxenus species use different hosts, and some samples seem to cluster by host species rather than by geographical distance.