We used phylogenetic analyses of cytochrome b sequences of malaria parasites and their avian hosts to assess the coevolutionary relationships between host and parasite lineages. Many lineages of avian malaria parasites have broad host distributions, which tend to obscure cospeciation events. The hosts of a single parasite or of closely related parasites were nonetheless most frequently recovered from members of the same host taxonomic family, more so than expected by chance. However, global assessments of the relationship between parasite and host phylogenetic trees, using Component and ParaFit, failed to detect significant cospeciation. The event-based approach employed by TreeFitter revealed significant cospeciation and duplication with certain cost assignments for these events, but host switching was consistently more prominent in matching the parasite tree to the host tree. The absence of a global cospeciation signal despite conservative host distribution most likely reflects relatively frequent acquisition of new hosts by individual parasite lineages. Understanding these processes will require a more refined species concept for malaria parasites and more extensive sampling of parasite distributions across hosts. If parasites can disperse between allopatric host populations through alternative hosts, cospeciation may not have a strong influence on the architecture of host–parasite relationships. Rather, parasite speciation may happen more often in conjunction with the acquisition of new hosts followed by divergent selection between host lineages in sympatry. Detailed studies of the phylogeographic distributions of hosts and parasites are needed to characterize these events.