Interactions of killer cell immunoglobulin-like receptors (KIRs) with major histocompatibility complex (MHC) class I ligands diversify natural killer cell responses to infection. By analyzing sequence variation in diverse human populations, we show that the KIR3DL1/S1 locus encodes two lineages of polymorphic inhibitory KIR3DL1 allotypes that recognize Bw4 epitopes of protein">HLA-A and HLA-B and one lineage of conserved activating KIR3DS1 allotypes, also implicated in Bw4 recognition. Balancing selection has maintained these three lineages for over 3 million years. Variation was selected at D1 and D2 domain residues that contact HLA class I and at two sites on D0, the domain that enhances the binding of KIR3D to HLA class I. HLA-B variants that gained Bw4 through interallelic microconversion are also products of selection. A worldwide comparison uncovers unusual KIR3DL1/S1 evolution in modern sub-Saharan Africans. Balancing selection is weak and confined to D0, KIR3DS1 is rare and KIR3DL1 allotypes with similar binding sites predominate. Natural killer cells express the dominant KIR3DL1 at a high frequency and with high surface density, providing strong responses to cells perturbed in Bw4 expression.