In arms races with parasites, hosts can evolve defences exhibiting extensive variability within populations, which signals individual identity ('signatures'). However, few such systems have evolved, suggesting that the conditions for their evolution are uncommon. We review (a) polymorphic egg markings that allow hosts of brood-parasitic birds to recognize and reject parasitic eggs, and (b) polymorphic tissue antigens encoded in the major histocompatibility complex (MHC), which present self- and pathogen-derived peptides to T cells of the immune system. Despite the profound differences between these systems, they share analogous features: (i) self/non-self discrimination by a highly specific recognition system (bird eyes and T-cell antigen receptor, respectively), which antagonists may escape by evolving evasion or mimicry; (ii) a self substrate upon which diversifying selection can act (eggs, and MHC molecules); (iii) acquired knowledge of self (resulting in acceptance of own eggs, and immune tolerance); and (iv) fitness costs associated with attack on self or lack of parasite detection. We suggest that these features comprise a set of requirements for parasites to drive the evolution of identity signatures in hosts, which diminish the likelihood of recognition errors. This may help to explain the variety of trajectories arising from arms races in different antagonistic contexts. This article is part of the theme issue 'The coevolutionary biology of brood parasitism: from mechanism to pattern'.