Maternal inheritance via the female-specific W chromosome was long ago proposed as a potential solution to the evolutionary enigma of co-existing host-specific races (or 'gentes') in avian brood parasites. Here we report the first unambiguous evidence for maternal inheritance of egg colouration in the brood-parasitic common cuckoo Cuculus canorus. Females laying blue eggs belong to an ancient (∼2.6 Myr) maternal lineage, as evidenced by both mitochondrial and W-linked DNA, but are indistinguishable at nuclear DNA from other common cuckoos. Hence, cuckoo host races with blue eggs are distinguished only by maternally inherited components of the genome, which maintain host-specific adaptation despite interbreeding among males and females reared by different hosts. A mitochondrial phylogeny suggests that blue eggs originated in Asia and then expanded westwards as female cuckoos laying blue eggs interbred with the existing European population, introducing an adaptive trait that expanded the range of potential hosts.