Tumor Associated Antigens (TAAs) may suffer from an immunological tolerance due to expression on normal cells. In order to potentiate their immunogenicity, heteroclitic peptides (htcPep) were designed according to prediction algorithms. In particular, specific modifications were introduced in peptide residues facing to TCR. Moreover, a MHC-optimized scaffold was designed for improved antigen presentation to TCR by H-2Db allele. The efficacy of such htcPep was assessed in C57BL/6 mice injected with syngeneic melanoma B16F10 or lung TC1 tumor cell lines, in combination with metronomic chemotherapy and immune checkpoint inhibitors. The immunogenicity of htcPep was significantly stronger than the corresponding wt peptide and the modification involving both MHC and TCR binding residues scored the strongest. In particular, the H-2Db-specific scaffold significantly potentiated the peptides’ immunogenicity and control of tumor growth was comparable to wt peptide in a therapeutic setting. Overall, we demonstrated that modified TAAs show higher immunogenicity compared to wt peptide. In particular, the MHC-optimized scaffold can present different antigen sequences to TCR, retaining the conformational characteristics of the corresponding wt. Cross-reacting CD8⁺T cells are elicited and efficiently kill tumor cells presenting the wild-type antigen. This novel approach can be of high clinical relevance in cancer vaccine development.