The use of “anchor-fixed” altered peptide ligands is of considerable interest in the development of therapeutic vaccines for cancer and infectious diseases, but the mechanism by which successful altered peptide ligands elicit enhanced immunity is unclear. In this study, we have determined the crystallographic structure of a major tumor rejection Ag, gp100 209–217, in complex with the HLA-A* 0201 (HLA-A2) molecule, as well as the structure of a modified version of the peptide which substitutes methionine for threonine at position 2 (T2M; gp100 209–2M). The T2M-modified peptide, which is more immunogenic in vitro and in vivo, binds HLA-A2 with a∼ 9-fold greater affinity and has a∼ 7-fold slower dissociation rate at physiological temperature. Within the limit of the crystallographic data, the T2M substitution does not alter the structure of the peptide/HLA-A2 complex. Consistent with this finding, in peripheral blood from 95 human subjects, we were unable to identify higher frequencies of T cells specific for either the native or modified peptide. These data strongly support the conclusion that the greater immunogenicity of the gp100 209–2M peptide is due to the enhanced stability of the peptide/MHC complex, validating the anchor-fixing approach for generating therapeutic vaccine candidates. Thermodynamic data suggest that the enhanced stability of the T2M-modified peptide/HLA-A2 complex is attributable to the increased hydrophobicity of the modified peptide, but the gain due to hydrophobicity is offset considerably by the loss of a hydrogen bond made by the native peptide to the HLA-A2 molecule. Our findings have broad implications for the optimization of current vaccine-design strategies.