The recognition of human leukocyte antigen (HLA)-E by the heterodimeric CD94-NKG2 natural killer (NK) receptor family is a central innate mechanism by which NK cells monitor the expression of other HLA molecules, yet the structural basis of this highly specific interaction is unclear. Here, we describe the crystal structure of CD94-NKG2A in complex with HLA-E bound to a peptide derived from the leader sequence of HLA-G. The CD94 subunit dominated the interaction with HLA-E, whereas the NKG2A subunit was more peripheral to the interface. Moreover, the invariant CD94 subunit dominated the peptide-mediated contacts, albeit with poor surface and chemical complementarity. This unusual binding mode was consistent with mutagenesis data at the CD94-NKG2A–HLA-E interface. There were few conformational changes in either CD94-NKG2A or HLA-E upon ligation, and such a “lock and key” interaction is typical of innate receptor–ligand interactions. Nevertheless, the structure also provided insight into how this interaction can be modulated by subtle changes in the peptide ligand or by the pairing of CD94 with other members of the NKG2 family. Differences in the docking strategies used by the NKG2D and CD94-NKG2A receptors provided a basis for understanding the promiscuous nature of ligand recognition by NKG2D compared with the fidelity of the CD94-NKG2 receptors.