Mutations within MHC class I-restricted epitopes have been studied in relation to T cell-mediated immune escape, but their impact on NK cells via interaction with killer Ig-like receptors (KIRs) during early HIV infection is poorly understood. In two patients acutely infected with HIV-1, we observed the appearance of a mutation within the B*57-restricted TW10 epitope (G9E) that did not facilitate strong escape from T cell recognition. The NK cell receptor KIR3DL1, carried by these patients, is known to recognize HLA-B*5703 and is associated with good control of HIV-1. Therefore, we tested whether the G9E mutation influenced the binding of HLA-B*5703 to soluble KIR3DL1 protein by surface plasmon resonance, and while the wild-type sequence and a second (T3N) variant were recognized, the G9E variant abrogated KIR3DL1 binding. We extended the study to determine the peptide sensitivity of KIR3DL1 interaction with epitopes carrying mutations near the C termini of TW10 and a second HLA-B*57-restricted epitope, IW9. Several amino acid changes interfered with KIR3DL1 binding, the most extreme of which included the G9E mutation commonly selected by HLA-B*57. Our results imply that during HIV-1 infection, some early-emerging variants could affect KIR-HLA interaction, with possible implications for immune recognition.