Plasmodium falciparum, the causative agent of the deadliest form of malaria, is a member of the Laverania subgenus, which includes ape-infecting parasites. P. falciparum is thought to have originated in gorillas, although infection is now restricted to humans. Laverania parasites display remarkable host-specificity, which is partially mediated by the interaction between parasite ligands and host receptors. We analyse the evolution of BSG (basigin) and GYPA (glycophorin A) in primates/hominins, as well as of their Plasmodium-encoded ligands, PfRH5 and PfEBA175. We show that, in primates, positive selection targeted two sites in BSG (F27 and H102), both involved in PfRH5 binding. A population genetics–phylogenetics approach detected the strongest selection for the gorilla lineage: one of the positively selected sites (K191) is a major determinant of PfRH5 binding affinity. Analysis of RH5 genes indicated episodic selection on the P. falciparum branch; the positively selected W447 site is known to stabilize the interaction with human basigin. Conversely, we detect no selection in the receptor-binding region of EBA175 in the P. falciparum lineage. Its host receptor, GYPA, shows evidence of positive selection in all hominid lineages; selected codons include glycosylation sites that modulate PfEBA175 binding affinity. Data herein provide an evolutionary explanation for species-specific binding of the PfRH5-BSG ligand–receptor pair and support the hypothesis that positive selection at these genes drove the host shift leading to the emergence of P. falciparum as a human pathogen.