Plasmodium falciparum is the most prevalent and lethal of the malaria parasites infecting humans, yet the origin and evolutionary history of this important pathogen remain controversial. Here we develop a single-genome amplification strategy to identify and characterize Plasmodium spp. DNA sequences in faecal samples from wild-living apes. Among nearly 3,000 specimens collected from field sites throughout central Africa, we found Plasmodium infection in chimpanzees (Pan troglodytes) and western gorillas (Gorilla gorilla), but not in eastern gorillas (Gorilla beringei) or bonobos (Pan paniscus). Ape plasmodial infections were highly prevalent, widely distributed and almost always made up of mixed parasite species. Analysis of more than 1,100 mitochondrial, apicoplast and nuclear gene sequences from chimpanzees and gorillas revealed that 99% grouped within one of six host-specific lineages representing distinct Plasmodium species within the subgenus Laverania. One of these from western gorillas comprised parasites that were nearly identical to P. falciparum. In phylogenetic analyses of full-length mitochondrial sequences, human P. falciparum formed a monophyletic lineage within the gorilla parasite radiation. These findings indicate that P. falciparum is of gorilla origin and not of chimpanzee, bonobo or ancient human origin.