Natural killer (NK) cells have an important role in immune defense against viruses and cancer. Activation of human NK cell cytotoxicity toward infected or tumor cells is regulated by killer cell immunoglobulin-like receptors (KIRs) that bind to human leukocyte antigen class I (HLA-I). Combinations of KIR with HLA-I are genetically associated with susceptibility to disease. KIR2DS4, an activating member of the KIR family with poorly defined ligands, is a receptor of unknown function. Here, we show that KIR2DS4 has a strong preference for rare peptides carrying a Trp at position 8 (p8) of 9-mer peptides bound to HLA-C*05:01. The complex of a peptide bound to HLA-C*05:01 with a Trp at p8 was sufficient for activation of primary KIR2DS4+ NK cells, independent of activation by other receptors and of prior NK cell licensing. HLA-C*05:01+ cells that expressed the peptide epitope triggered KIR2DS4+ NK cell degranulation. We show an inverse correlation of the worldwide allele frequency of functional KIR2DS4 with that of HLA-C*05:01, indicative of functional interaction and balancing selection. We found a highly conserved peptide sequence motif for HLA-C*05:01–restricted activation of human KIR2DS4+ NK cells in bacterial recombinase A (RecA). KIR2DS4+ NK cells were stimulated by RecA epitopes from multiple human pathogens, including Helicobacter, Chlamydia, Brucella, and Campylobacter. We predict that over 1,000 bacterial species could activate NK cells through KIR2DS4, and propose that human NK cells also contribute to immune defense against bacteria through recognition of a conserved RecA epitope presented by HLA-C*05:01.