Objective: The objective of this study is to identify human leukocyte antigen (HLA) class I and killer-cell immunoglobulin-like receptor (KIR) genotypes associated with different risks for HIV acquisition and HIV disease progression. Design: A cross-sectional study of a cohort of 468 high-risk individuals (246 HIV-positive and 222 HIV-negative) from outpatient clinics in Lima (Perú). Methods: The cohort was high-resolution HLA and KIR-typed and analysed for potential differences in single-allele frequencies and allele combinations between HIV-positive and HIV-negative individuals and for associations with HIV viral load and CD4+ cell counts in infected individuals. Results: HLA class I alleles associated with a lack of viral control had a significantly higher population frequency than relatively protective alleles (P = 0.0093), in line with a rare allele advantage. HLA-A∗02 : 01 and HLA-C∗04 : 01 were both associated with high viral loads (P = 0.0313 and 0.0001, respectively) and low CD4+ cell counts (P = 0.0008 and 0.0087, respectively). Importantly, the association between HLA-C∗04 : 01 and poor viral control was not due to its linkage disequilibrium with other HLA alleles. Rather, the coexpression of its putative KIR ligand KIR2DS4f was critically linked to elevated viral loads. Conclusion: These results highlight the impact of population allele frequency on viral control and identify a novel association between HLA-C∗04 : 01 in combination with KIR2DS4f and uncontrolled HIV infection. Our data further support the importance of the interplay of markers of the adaptive and innate immune system in viral control.