Social parasitism in insects has raised major questions in evolutionary biology, firstly in terms of adaptations that parasites use to circumvent host defenses and, secondly, in terms of whether social parasites have arisen via allopatric or sympatric speciation. Here, we raise a third and major evolutionary issue: a priori considerations suggest that social parasites have much smaller effective population sizes (Ne) than their hosts, and should therefore have much slower rates of evolution than their hosts. The evolutionary arms race should therefore be weighted in favor of host species, raising the question of how social parasites have been able to persist over evolutionary time? Very few studies, however, have actually estimated the relative sizes of Ne for social insects and their social parasites, and therefore the dimensions of unequal host-parasite evolutionary rates are unknown. Here, we use extensive samples of allodapine bee host species and their inquilines from two localities over multiple years to gage their relative Nes. We show that inquiline species have Nes that are about an order of magnitude lower than their hosts, so explaining the evolutionary persistence of social parasitism poses a major puzzle for evolutionary biology. We propose several hypotheses that may be able to address this puzzle and discuss how they could be evaluated.