We have determined high-resolution crystal structures of the complexes of HLA-A2 molecules with two modified immunodominant peptides from the melanoma tumor-associated protein Melan-A/Melanoma Ag recognized by T cells-1. The two peptides, a decamer and nonamer with overlapping sequences (ELAGIGILTV and ALGIGILTV), are modified in the second residue to increase their affinity for HLA-A2. The modified decamer is more immunogenic than the natural peptide and a candidate for peptide-based melanoma immunotherapy. The crystal structures at 1.8 and 2.15 A resolution define the differences in binding modes of the modified peptides, including different clusters of water molecules that appear to stabilize the peptide-HLA interaction. The structures suggest both how the wild-type peptides would bind and how three categories of cytotoxic T lymphocytes with differing fine specificity might recognize the two peptides.