Most vaccines are based on protective humoral responses while for intracellular pathogens CD8(+) T cells are regularly needed to provide protection. However, poor processing efficiency of antigens is often a limiting factor in CD8(+) T cell priming, hampering vaccine efficacy. The multistage cDNA vaccine H56, encoding three secreted Mycobacterium tuberculosis antigens, was used to test a complete strategy to enhance vaccine' immunogenicity. Potential CD8(+) T cell epitopes in H56 were predicted using the NetMHC3.4/ANN program. Mice were immunized with H56 cDNA using dermal DNA tattoo immunization and epitope candidates were tested for recognition by responding CD8(+) T cells in ex vivo assays. Seven novel CD8(+) T cell epitopes were identified. H56 immunogenicity could be substantially enhanced by two strategies: (i) fusion of the H56 sequence to cDNA of proteins that modify intracellular antigen processing or provide CD4(+) T cell help, (ii) by substitution of the epitope's hydrophobic C-terminal flanking residues for polar glutamic acid, which facilitated their proteasome-mediated generation. We conclude that this whole strategy of in silico prediction of potential CD8(+) T cell epitopes in novel antigens, followed by fusion to sequences with immunogenicity-enhancing properties or modification of epitope flanking sequences to improve proteasome-mediated processing, may be exploited to design novel vaccines against emerging or 'hard to treat' intracellular pathogens.