Genetic vaccines are emerging as a powerful modality to induce T-cell responses to target tumor associated antigens (TAA). Viral or plasmid DNA or RNA vectors harbor an expression cassette encoding the antigen of choice delivered in vivo by vaccination. In this context, immunizations with minigenes containing selected, highly antigenic, T-cell epitopes of TAAs may have several advantages relative to full-length proteins. The objective of this study was to identify an optimal scaffold for minigene construction. We generated a number of minigenes containing epitopes from the carcinoembryonic antigen (CEA) model TAA and utilized muscle DNA electro-gene-transfer (DNA-EGT) to vaccinate HLA-A*0201 (HHD) and CEA/HHD double transgenic mice. The components utilized to construct the minigenes included CD8 T cell epitopes and (or) anchor modified analogs that were selected on the basis of their predicted binding to HLA-*A0201, their uniqueness in the human proteome, and the likelihood of cancer cell natural processing and presentation via MHC-I. Other candidate components comparatively tested included: helper CD4 T-cell epitopes, flanking regions for optimal epitope processing (including both proteasome-dependent and furin-dependent polypeptide processing mechanisms), and immunoenhancing moieties. Through a series of comparative studies and iterations we have identified an optimal minigene scaffold comprising the following elements: human tissue plasminogen activator (TPA) signal peptide, T-cell epitopes connected by furin sensitive linkers, and the enterotoxin B subunit. The selected epitope modified minigenes (EMM) delivered by DNA-EGT were able to break immune tolerance in CEA/HHD mice and induce a strong immune response against all epitopes tested, independently of their relative positions within the scaffold. Furthermore, the optimized EMMs delivered via DNA-EGT were more immunogenic and exerted more powerful antitumor effects in a B16-CEA/HHD metastatic melanoma model than a DNA vector encoding the full-length protein or a mixture of the same peptides injected subcutaneously. Our data may shed light on the optimal design of a universal vehicle for epitope-targeted, genetic cancer vaccines.