Progress in human tumor immunology has recently been accelerated by new assays for antigen‐specific cytotoxic T lymphocytes (CTLs). We have used tetrameric MHC class I complexes (tetramers) to study melanoma‐specific CTLs both in vivo and in vitro, and have utilized the results to optimize vaccination strategies for patients. Tetramers have provided some of the best evidence to date that CTL responses against melanoma antigens arise spontaneously in patients. However, CTL responses to common (nonmutated) melanoma epitopes are generally weak or localized, and occur mostly in advanced metastatic disease, hence justifying early immunotherapeutic approaches. These observations led us to design a polyvalent vaccine construct for early administration to melanoma patients at high risk of progression. To compare possible vaccination protocols, we encoded this construct in several different vectors, and developed novel tetramers to track responses to the human melanoma epitopes in transgenic mice. Priming and boosting with the same poly‐epitope construct encoded in heterologous vectors led to the expansion of CTLs with a single dominant specificity. Separating the antigens for independent presentation by antigen‐presenting cells reversed the effect of immunodominance and induced a powerful polyvalent CTL response. These results provide important pointers for future vaccination trials, and tetramers will form an important tool in the immunomonitoring of these clinical studies.