Human leukocyte antigen (HLA)-E is a non-classical major histocompatibility complex class I molecule that binds peptides derived from the leader sequences of other HLA class I molecules. Natural killer cell recognition of these HLA-E molecules, via the CD94–NKG2 natural killer family, represents a central innate mechanism for monitoring major histocompatibility complex expression levels within a cell. The leader sequence-derived peptides bound to HLA-E exhibit very limited polymorphism, yet subtle differences affect the recognition of HLA-E by the CD94–NKG2 receptors. To better understand the basis for this peptide-specific recognition, we determined the structure of HLA-E in complex with two leader peptides, namely, HLA-Cw*07 (VMAPRALLL), which is poorly recognised by CD94–NKG2 receptors, and HLA-G*01 (VMAPRTLFL), a high-affinity ligand of CD94–NKG2 receptors. A comparison of these structures, both of which were determined to 2.5-Å resolution, revealed that allotypic variations in the bound leader sequences do not result in conformational changes in the HLA-E heavy chain, although subtle changes in the conformation of the peptide within the binding groove of HLA-E were evident. Accordingly, our data indicate that the CD94–NKG2 receptors interact with HLA-E in a manner that maximises the ability of the receptors to discriminate between subtle changes in both the sequence and conformation of peptides bound to HLA-E.