Epitope-based vaccination strategies designed to induce tumor-specific CD8 CTL are being widely considered for cancer immunotherapy. Here we describe a recombinant poxvirus vaccine that codes for ten HLA-A2-restricted epitopes derived from five melanoma Ags conjoined in an artificial polyepitope or polytope construct. Target cells infected with the melanoma polytope vaccinia were recognized by three different epitope-specific CTL lines derived from HLA-A2 melanoma patients, and CTL responses to seven of the epitopes were generated in at least one of six HLA-A2-transgenic mice immunized with the construct. CTL lines derived from vaccinated transgenic mice were also able to kill melanoma cells in vitro. Multiple epitopes within the polytope construct were therefore shown to be individually immunogenic, illustrating the feasibility of the polytope approach for melanoma immunotherapy. Tumor escape from CTL surveillance, through down regulation of individual tumor Ags and MHC alleles, might be overcome by polytope vaccines, which simultaneously target multiple cancer Ags.