Immune therapy has provided a significant breakthrough in the treatment of metastatic melanoma. Despite the remarkable clinical efficacy and established involvement of effector CD8 T cells, the knowledge of the exact peptide-MHC complexes recognized by T cells on the tumor cell surface is limited. Many melanoma-associated T-cell epitopes have been described, but this knowledge remains largely restricted to HLA-A2, and we lack understanding of the T-cell recognition in the context of other HLA molecules. We selected six melanoma-associated antigens (MAGE-A3, NY-ESO-1, gp100, Mart1, tyrosinase and TRP-2) that are frequently recognized in patients with the aim of identifying novel T-cell epitopes restricted to HLA-A1, -A3, -A11 and -B7. Using in silico prediction and in vitro confirmation, we identified 127 MHC ligands and analyzed the T-cell responses against these ligands via the MHC multimer-based enrichment of peripheral blood from 39 melanoma patients and 10 healthy donors. To dissect the T-cell reactivity against this large peptide library, we used combinatorial-encoded MHC multimers and observed the T-cell responses against 17 different peptide-MHC complexes in the patient group and four in the healthy donor group. We confirmed the processing and presentation of HLA-A3-restricted T-cell epitopes from tyrosinase (TQYESGSMDK) and gp100 (LIYRRRLMK) and an HLA-A11-restricted T-cell epitope from gp100 (AVGATKVPR) via the cytolytic T-cell recognition of melanoma cell lines and/or K562 cells expressing the appropriate antigen and HLA molecule. We further found T-cell reactivity against two of the identified sequences among tumor-infiltrating lymphocytes from melanoma patients, suggesting a potential clinical relevance of these sequences.