Host traits, such as migratory behavior, could facilitate the dispersal of disease-causing parasites, potentially leading to the transfer of infections both across geographic areas and between host species. There is, however, little quantitative information on whether variation in such host attributes does indeed affect the evolutionary outcome of host-parasite associations. Here, we employ Leucocytozoon blood parasites of birds, a group of parasites closely related to avian malaria, to study host-parasite coevolution in relation to host behavior using a phylogenetic comparative approach. We reconstruct the molecular phylogenies of both the hosts and parasites and use cophylogenetic tools to assess whether each host-parasite association contributes significantly to the overall congruence between the two phylogenies. We find evidence for a significant fit between host and parasite phylogenies in this system, but show that this is due only to associations between nonmigrant parasites and their hosts. We also show that migrant bird species harbor a greater genetic diversity of parasites compared with nonmigrant species. Taken together, these results suggest that the migratory habits of birds could influence their coevolutionary relationship with their parasites, and that consideration of host traits is important in predicting the outcome of coevolutionary interactions.