Host immunity exerts strong selective pressure on pathogens. Population-level genetic analysis can identify signatures of this selection, but these signatures reflect the net selective effect of all hosts and vectors in a population. In contrast, analysis of pathogen diversity within hosts provides information on individual, host-specific selection pressures. Here, we combine these complementary approaches in an analysis of the malaria parasite Plasmodium falciparum using haplotype sequences from thousands of natural infections in sub-Saharan Africa. We find that parasite genotypes show preferential clustering within multi-strain infections in young children, and identify individual amino acid positions that may contribute to strain-specific immunity. Our results demonstrate that natural host defenses to P. falciparum act in an allele-specific manner to block specific parasite haplotypes from establishing blood-stage infections. This selection partially explains the extreme amino acid diversity of many parasite antigens and suggests that vaccines targeting such proteins should account for allele-specific immunity.