Adaptive evolutionary theory argues that organisms with larger effective population size (Ne) should have higher rates of adaptive evolution and therefore greater capacity to win evolutionary arm races. However, in some certain cases species with much smaller Ne may be able to survive beside their opponents for an extensive evolutionary time. Neutral theory predicts that accelerated rates of molecular evolution in organisms with exceedingly small Ne is due to the effects of genetic drift and fixation of slightly deleterious mutations. We test this prediction in two obligate social parasite species and their respective host species from the bee tribe Allodapini. The parasites (genus Inquilina) have been locked into a tight coevolutionary arm races with their exclusive hosts (genus Exoneura) for ~15 million years, even though Inquilina exhibit Ne that are an order of magnitude smaller than their host. In this study, we compared rates of molecular evolution between host and parasite using nonsynonymous to synonymous substitution rate ratios (dN/dS) of eleven mitochondrial protein coding genes sequenced from transcriptomes. Tests of selection on mitochondrial genes indicated no significant differences between host and parasite dN/dS, with evidence for purifying selection acting on all mitochondrial genes of host and parasite species. Several potential factors which could weaken the inverse relationship between Ne and rate of molecular evolution are discussed.