The phylogenetic relationships among hemosporidian parasites, including the origin of Plasmodium falciparum, the most virulent malaria parasite of humans, have been heavily debated for decades. Studies based on multiple-gene sequences have helped settle many of these controversial phylogenetic issues. However, denser taxon sampling and genome-wide analyses are needed to confidently resolve the evolutionay relationships among hemosporidian parasites. Genome sequences of several Plasmodium parasites are available but only for species infecting primates and rodents. To root the phylogenetic tree of Plasmodium, genomic data from related parasites of birds or reptiles are required. Here, we use a novel approach to isolate parasite DNA from microgametes and describe the first genome of a bird parasite in the sister genus to Plasmodium, Haemoproteus tartakovskyi Similar to Plasmodium parasites, H. tartakovskyi has a small genome (23.2 Mb, 5,990 genes) and a GC content (25.4%) closer to P. falciparum (19.3%) than to Plasmodium vivax (42.3%). Combined with novel transcriptome sequences of the bird parasite Plasmodium ashfordi, our phylogenomic analyses of 1,302 orthologous genes demonstrate that mammalian-infecting malaria parasites are monophyletic, thus rejecting the repeatedly proposed hypothesis that the ancestor of Laverania parasites originated from a secondary host shift from birds to humans. Genes and genomic features previously found to be shared between P. falciparum and bird malaria parasites, but absent in other mammal malaria parasites, are therefore signatures of maintained ancestral states. We foresee that the genome of H. tartakovskyi will open new directions for comparative evolutionary analyses of malarial adaptive traits.