We studied the phylogeny of avian haemosporidian parasites, Haemoproteus and Plasmodium, in a number of African resident and European migratory songbird species sampled during spring and autumn in northern Nigeria. The phylogeny of the parasites was constructed through sequencing part of their mitochondrial cytochrome b gene. We found eight parasite lineages, five Haemoproteus and three Plasmodium, infecting multiple host species. Thus, 44% of the 18 haemospiridian lineages found in this study were detected in more than one host species, indicating that host sharing is a more common feature than previously thought. Furthermore, one of the Plasmodium lineages infected species from different host families, Sylviidae and Ploceidae, expressing exceptionally large host range. We mapped transmission events, e.g. the occurrence of the parasite lineages in resident bird species in Europe or Africa, onto a phylogenetic tree. This yielded three clades, two Plasmodium and one Haemoproteus, in which transmission seems to occur solely in Africa. One Plasmodium clade showed European transmission, whereas the remaining two Haemoproteus clades contained mixes of lineages of African, European or unknown transmission. The mix of areas of transmission in several branches of the phylogenetic tree suggests that transmission of haemosporidian parasites to songbirds has arisen repeatedly in Africa and Europe. Blood parasites could be viewed as a cost of migration, as migratory species in several cases were infected with parasite lineages from African resident species. This cost of migration could have considerable impact on the evolution of migration and patterns of winter distribution in migrating birds.