The geographical origin of Plasmodium vivax, the most widespread human malaria parasite, is controversial. Although genetic closeness to Asian primate malarias has been confirmed by phylogenetic analyses, genetic similarities between P. vivax and Plasmodium simium, a New World primate malaria, suggest that humans may have acquired P. vivax from New World monkeys or vice versa. Additionally, the near fixation of the Duffy-negative blood type (FY x B(null)/FY x B(null)) in West and Central Africa, consistent with directional selection, and the association of Duffy negativity with complete resistance to vivax malaria suggest a prolonged period of host-parasite coevolution in Africa. Here we use Bayesian and likelihood methods in conjunction with cophylogeny mapping to reconstruct the genetic and coevolutionary history of P. vivax from the complete mitochondrial genome of 176 isolates as well as several closely related Plasmodium species. Taken together, a haplotype network, parasite migration patterns, demographic history, and cophylogeny mapping support an Asian origin via a host switch from macaque monkeys.