Natural killer (NK) cells provide defense in the early stages of the innate immune response against viral infections by producing cytokines and causing cytotoxicity. The killer immunoglobulin-like receptors (KIRs) on NK cells regulate the inhibition and activation of NK-cell responses through recognition of human leukocyte antigen (HLA) class I molecules on target cells KIR and HLA loci are both highly polymorphic, and some HLA class I products bind and trigger cell-surface receptors specified by KIR genes. Here we report that the activating KIR allele KIR3DS1, in combination with HLA-B alleles that encode molecules with isoleucine at position 80 (HLA-B Bw4-80Ile), is associated with delayed progression to AIDS in individuals infected with human immunodeficiency virus type 1 (HIV-1). In the absence of KIR3DS1, the HLA-B Bw4-80Ile allele was not associated with any of the AIDS outcomes measured. By contrast, in the absence of HLA-B Bw4-80Ile alleles, KIR3DS1 was significantly associated with more rapid progression to AIDS. These observations are strongly suggestive of a model involving an epistatic interaction between the two loci. The strongest synergistic effect of these loci was on progression to depletion of CD4(+) T cells, which suggests that a protective response of NK cells involving KIR3DS1 and its HLA class I ligands begins soon after HIV-1 infection.