We report a phylogenetic analysis of primate malaria parasites based on the gene encoding the cytochrome b protein from the mitochondrial genome. We have studied 17 species of Plasmodium, including 14 parasitic in primates. In our analysis, four species were used for rooting the Plasmodium phylogenetic tree: two from closely related genera (Hepatocystis sp. and Haemoproteus columbae) and two other Apicomplexa (Toxoplasma gondii and Theileria parva). We found that primate malaria parasites form a monophyletic group, with the only exception being the Plasmodium falciparum-Plasmodium reichenowi lineage. Phylogenetic analyses that include two species of non-Plasmodium Haemosporina suggest that the genus Plasmodium is polyphyletic. We conclude that the biologic traits, such as periodicity and the capacity to relapse, have limited value for assessing the phylogenetic relationships among Plasmodium species. For instance, we found no evidence that would link virulence with the age of the host-parasite association. Our studies also reveal that the primate malaria parasites originated in Africa, which contradicts the presently held opinion of Southeast Asia as their center of origin. We propose that the radiation of Asian monkey parasites is a recent event where several life history traits, like differences in periodicity, appeared de novo.