Allotypes of the natural killer (NK) cell receptor KIR3DL1 vary in both NK cell expression patterns and inhibitory capacity upon binding to their ligands, HLA-B Bw4 molecules, present on target cells. Using a sample size of over 1,500 human immunodeficiency virus (HIV)+ individuals, we show that various distinct allelic combinations of the KIR3DL1 and HLA-B loci significantly and strongly influence both AIDS progression and plasma HIV RNA abundance in a consistent manner. These genetic data correlate very well with previously defined functional differences that distinguish KIR3DL1 allotypes. The various epistatic effects observed here for common, distinct KIR3DL1 and HLA-B Bw4 combinations are unprecedented with regard to any pair of genetic loci in human disease, and indicate that NK cells may have a critical role in the natural history of HIV infection.