Tyrosinase was the first melanoma-associated antigen shown to be recognized by CD4+ T cells. In this study, we have identified two HLA-DRB1*0401-restricted peptides recognized by these T cells: Ty 56-70 and Ty 448-462. As with many of the MHC class I-restricted melanoma epitopes, both are nonmutated self peptides that have intermediate and weak MHC binding affinities, respectively. Mutated and truncated versions of these peptides were used to define their MHC binding anchor residues. Anchor residues were then modified to derive peptides with increased MHC binding affinities and T cell stimulatory properties. Ty 56-70 and Ty 448-462 enhance the list of immunogenic HLA-A2-, A24-, and B44-restricted tyrosinase peptides already described. Thus, tyrosinase provides a model for anti-melanoma vaccines in which a single molecule can generate multivalent immunization incorporating both CD4+ and CD8+ T cell responses.