We examined the mitogenomes of a large global collection of human malaria parasites to explore how and when Plasmodium falciparum and P. vivax entered the Americas. We found evidence of a significant contribution of African and South Asian lineages to present-day New World malaria parasites with additional P. vivax lineages appearing to originate from Melanesia that were putatively carried by the Australasian peoples who contributed genes to Native Americans. Importantly, mitochondrial lineages of the P. vivax-like species P. simium are shared by platyrrhine monkeys and humans in the Atlantic Forest ecosystem, but not across the Amazon, which most likely resulted from one or a few recent human-to-monkey transfers. While enslaved Africans were likely the main carriers of P. falciparum mitochondrial lineages into the Americas after the conquest, additional parasites carried by Australasian peoples in pre-Columbian times may have contributed to the extensive diversity of extant local populations of P. vivax.