When mimicry imposes costs on models, selection may drive the model's phenotype to evolve away from its mimic. For example, brood parasitism often drives hosts to diversify in egg appearance among females within a species, making mimetic parasitic eggs easier to detect. However, when a single parasite species exploits multiple host species, parasitism could also drive host egg evolution away from other co-occurring hosts, to escape susceptibility to their respective mimics. This hypothesis predicts that sympatric hosts of the same parasite should partition egg phenotypic space (defined by egg colour, luminance and pattern) among species to avoid one another. We show that eggs of warbler species parasitized by the cuckoo finch Anomalospiza imberbis in Zambia partition phenotypic space much more distinctly than do eggs of sympatric but unparasitized warblers. Correspondingly, cuckoo finch host-races better match their own specialist host than other local host species. In the weaver family, parasitized by the diederik cuckoo Chrysococcyx caprius, by contrast, parasitized species were more closely related and overlapped extensively in phenotypic space; correspondingly, cuckoos did not match their own host better than others. These results suggest that coevolutionary arms races between hosts and parasites may be shaped by the wider community context in which they unfold.