The non-classical class Ib molecule human leukocyte antigen E (HLA-E) has limited polymorphism and can bind HLA class Ia leader peptides (VL9). HLA-E-VL9 complexes interact with the natural killer (NK) cell receptors NKG2A-C/CD94 and regulate NK cell-mediated cytotoxicity. Here we report the isolation of 3H4, a murine HLA-E-VL9-specific IgM antibody that enhances killing of HLA-E-VL9-expressing cells by an NKG2A+ NK cell line. Structural analysis reveal that 3H4 acts by preventing CD94/NKG2A docking on HLA-E-VL9. Upon in vitro maturation, an affinity-optimized IgG form of 3H4 showes enhanced NK killing of HLA-E-VL9-expressing cells. HLA-E-VL9-specific IgM antibodies similar in function to 3H4 are also isolated from naïve B cells of cytomegalovirus (CMV)-negative, healthy humans. Thus, HLA-E-VL9-targeting mouse and human antibodies isolated from the naïve B cell antibody pool have the capacity to enhance NK cell cytotoxicity.