Although various immune checkpoint inhibitors (ICIs), used for the treatment of advanced cancer, showed remarkably durable tumor regression in a subset of patients, there are important limitations in a large group of non-responders, and the generation of novel immunogens capable of inducing protective cellular immune responses is a priority in cancer immunotherapy field. During the last decades, several types of vaccine immunogens have been used in numerous preclinical studies and clinical trials. However, although immunity to tumor Ags can be elicited by most vaccines tested, their clinical efficacy remains modest. Recently, we have developed an innovative vaccine concept, called Variable Epitope Libraries (VELs), with the purpose to exploit the high antigenic variability of many important pathogens and tumor cells as starting points for the construction of a new class of vaccine immunogens capable of inducing the largest possible repertoire of both B and T cells. In the present study, we decided to generate VEL immunogens derived from both classical and non-classical major histocompatibility complex (MHC) class I molecules. The MHC molecules, responsible for antigen presentation and subsequent activation of T lymphocytes, undergo multiple modifications that directly affect their proper function, resulting in immune escape of tumor cells. Two large VELs derived from multi-epitope region of H2-Kd and Qa-2 sequences (46 and 34 amino acids long, respectively), along with their wild type counterparts have been generated as synthetic peptides and tested in an aggressive 4T1 mouse model of breast cancer. Significant inhibition of tumor growth and the reduction of metastatic lesions in the lungs of immunized mice were observed. This study demonstrated for the first time the successful application of VELs carrying combinatorial libraries of epitope variants derived from MHC class I molecules as novel vaccine immunogens.