In coevolutionary arms races, interacting species impose selection on each other, generating reciprocal adaptations and counter adaptations. This process is typically enhanced by genetic recombination and heterozygosity, but these sources of evolutionary novelty may be secondarily lost when uniparental inheritance evolves to ensure the integrity of sex-linked adaptations. We demonstrate that host-specific egg mimicry in the African cuckoo finch Anomalospiza imberbis is maternally inherited, confirming the validity of an almost century-old hypothesis. We further show that maternal inheritance not only underpins the mimicry of different host species but also additional mimetic diversification that approximates the range of polymorphic egg “signatures” that have evolved within host species as an escalated defense against parasitism. Thus, maternal inheritance has enabled the evolution and maintenance of nested levels of mimetic specialization in a single parasitic species. However, maternal inheritance and the lack of sexual recombination likely disadvantage cuckoo finches by stifling further adaptation in the ongoing arms races with their individual hosts, which we show have retained biparental inheritance of egg phenotypes. The inability to generate novel genetic combinations likely prevents cuckoo finches from mimicking certain host phenotypes that are currently favored by selection (e.g., the olive-green colored eggs laid by some tawny-flanked prinia, Prinia subflava, females). This illustrates an important cost of coding coevolved adaptations on the nonrecombining sex chromosome, which may impede further coevolutionary change by effectively reversing the advantages of sexual reproduction in antagonistic coevolution proposed by the Red Queen hypothesis.