The reproductive division of labour between queen and worker castes in social insects is a defining characteristic of eusociality and a classic example of phenotypic plasticity. Whether social insect larvae develop into queens or workers has long been thought to be determined by environmental cues, i.e. larvae are developmentally totipotent. Contrary to this paradigm, several recent studies have revealed that caste is determined by genotype in some ant species, but whether this is restricted to just a few exceptional species is still unclear. Here, we show that the Mediterranean harvester ant Messor barbarus possesses an unusual reproductive system, in which the female castes are genetically determined. Using both nuclear and mitochondrial data, we show that Iberian populations have two distinct, cryptic lineages. Workers are always inter-lineage hybrids whereas queens are always produced from pure-lineage matings. The results suggest that genetic caste determination may be more widespread in ants than previously thought, and that further investigation in other species is needed to understand the frequency and evolution of this remarkable reproductive system.