Background: Viruses can evade immune surveillance, but the underlying mechanisms are insufficiently understood. Here, we sought to understand the mechanisms by which natural killer (NK) cells recognize HIV-1-infected cells and how this virus can evade NK-cell-mediated immune pressure. Methods and Findings: Two sequence mutations in p24 Gag associated with the presence of specific KIR/HLA combined genotypes were identified in HIV-1 clade C viruses from a large cohort of infected, untreated individuals in South Africa (n = 392), suggesting viral escape from KIR+ NK cells through sequence variations within HLA class I—presented epitopes. One sequence polymorphism at position 303 of p24 Gag (TGag303V), selected for in infected individuals with both KIR2DL3 and HLA-C*03:04, enabled significantly better binding of the inhibitory KIR2DL3 receptor to HLA-C*03:04-expressing cells presenting this variant epitope compared to the wild-type epitope (wild-type mean 18.01 ± 10.45 standard deviation [SD] and variant mean 44.67 ± 14.42 SD, p = 0.002). Furthermore, activation of primary KIR2DL3+ NK cells from healthy donors in response to HLA-C*03:04+ target cells presenting the variant epitope was significantly reduced in comparison to cells presenting the wild-type sequence (wild-type mean 0.78 ± 0.07 standard error of the mean [SEM] and variant mean 0.63 ± 0.07 SEM, p = 0.012). Structural modeling and surface plasmon resonance of KIR/peptide/HLA interactions in the context of the different viral sequence variants studied supported these results. Future studies will be needed to assess processing and antigen presentation of the investigated HIV-1 epitope in natural infection, and the consequences for viral control. Conclusions: These data provide novel insights into how viruses can evade NK cell immunity through the selection of mutations in HLA-presented epitopes that enhance binding to inhibitory NK cell receptors. Better understanding of the mechanisms by which HIV-1 evades NK-cell-mediated immune pressure and the functional validation of a structural modeling approach will facilitate the development of novel targeted immune interventions to harness the antiviral activities of NK cells.