Coevolution is often invoked as an engine of biological diversity. Avian brood parasites and their hosts provide one of the best-known examples of coevolution. Brood parasites lay their eggs in the nests of other species, selecting for host defences and reciprocal counter-adaptations in parasites. In theory, this arms race should promote increased rates of speciation and phenotypic evolution. Here we use recently developed methods to test whether the three largest avian brood parasitic lineages show changes in rates of phenotypic diversity and speciation relative to non-parasitic lineages. Our results challenge the accepted paradigm, and show that there is little consistent evidence that lineages of brood parasites have higher speciation or extinction rates than non-parasitic species. However, we provide the first evidence that the evolution of brood parasitic behaviour may affect rates of evolution in morphological traits associated with parasitism. Specifically, egg size and the colour and pattern of plumage have evolved up to nine times faster in parasitic than non-parasitic cuckoos. Moreover, cuckoo clades of parasitic species that are sympatric (and share similar host genera) exhibit higher rates of phenotypic evolution. This supports the idea that competition for hosts may be linked to the high phenotypic diversity found in parasitic cuckoos.