Plasmodium species causing malaria in humans are not monophyletic, sharing common ancestors with nonhuman primate parasites. Plasmodium gonderi is one of the few known Plasmodium species infecting African old-world monkeys that are not found in apes. This study reports a de novo assembled P. gonderi genome with complete chromosomes. The P. gonderi genome shares codon usage, syntenic blocks, and other characteristics with the human parasites Plasmodium ovale s.l. and Plasmodium malariae, also of African origin, and the human parasite Plasmodium vivax and species found in nonhuman primates from Southeast Asia. Using phylogenetically aware methods, newly identified syntenic blocks were found enriched with conserved metabolic genes. Regions outside those blocks harbored genes encoding proteins involved in the vertebrate host-Plasmodium relationship undergoing faster evolution. Such genome architecture may have facilitated colonizing vertebrate hosts. Phylogenomic analyses estimated the common ancestor between P. vivax and an African ape parasite P. vivax-like, within the Asian nonhuman primates parasites clade. Time estimates incorporating P. gonderi placed the P. vivax and P. vivax-like common ancestor in the late Pleistocene, a time of active migration of hominids between Africa and Asia. Thus, phylogenomic and time-tree analyses are consistent with an Asian origin for P. vivax and an introduction of P. vivax-like into Africa. Unlike other studies, time estimates for the clade with Plasmodium falciparum, the most lethal human malaria parasite, coincide with their host species radiation, African hominids. Overall, the newly assembled genome presented here has the quality to support comparative genomic investigations in Plasmodium.