The antigenic variability of tumor cells leading to dynamic changes in cancer epitope landscape along with escape from immune surveillance by down-regulating tumor antigen expression/presentation and immune tolerance are major obstacles for the design of effective vaccines. We have developed a novel concept for immunogen construction based on introduction of massive mutations within the epitopes targeting antigenically variable pathogens and diseases. Previously, we showed that these immunogens carrying large combinatorial libraries of mutated epitope variants, termed as variable epitope libraries (VELs), induce potent, broad and long lasting CD8+IFN-γ+ T-cell response as well as HIV-neutralizing antibodies. In this proof-of-concept study, we tested immunogenic properties and anti-tumor effects of the VELs bearing survivin-derived CTL epitope (GWEPDDNPI) variants in an aggressive metastatic mouse 4T1 breast tumor model. The constructed VELs had complexities of 10,500 and 8,000 individual members, generated as combinatorial M13 phage display and synthetic peptide libraries, respectively, with structural composition GWXPXDXPI, where X is any of 20 natural amino acids. Statistically significant tumor growth inhibition was observed in BALB/c mice immunized with the VELs in both prophylactic and therapeutic settings. Vaccinated mice developed epitope-specific spleen cell and CD8+ IFN-γ+ T-cell responses that recognize more than 50% of the panel of 87 mutated epitope variants, as demonstrated in T-cell proliferation assays and FACS analysis. These data indicate the feasibility of the application of this new class of immunogens based on VEL concept as an alternative approach for the development of molecular vaccines against cancer.