A major hurdle in designing successful epitope-based vaccines resides in the delivery, stability, and immunogenicity of the peptide immunogen. The short-lived nature of unmodified peptide-based vaccines in vivo limits their therapeutic application in the immunotherapy of cancers and chronic viral infections as well as their use in generating prophylactic immunity. The incorporation of beta-amino acids into peptides decreases proteolysis, yet its potential application in the rational design of T cell mimotopes is poorly understood. To address this, we have replaced each residue of the SIINFEKL epitope individually with the corresponding beta-amino acid and examined the resultant efficacy of these mimotopes. Some analogs displayed similar MHC binding and superior protease stability compared with the native epitope. Importantly, these analogs were able to generate cross-reactive CTLs in vivo that were capable of lysing tumor cells that expressed the unmodified epitope as a surrogate tumor Ag. Structural analysis of peptides in which anchor residues were substituted with beta-amino acids revealed the basis for enhanced MHC binding and retention of immunogenicity observed for these analogs and paves the way for future vaccine design using beta-amino acids. We conclude that the rational incorporation of beta-amino acids into T cell determinants is a powerful alternative to the traditional homologous substitution of randomly chosen naturally occurring alpha-amino acids, and these mimotopes may prove particularly useful for inclusion in epitope-based vaccines.