We have generated a xenogeneic vaccine against human carcinoembryonic antigen (hCEACAM-5 or commonly hCEA) using as immunogen rhesus CEA (rhCEA). RhCEA cDNA was codon-usage optimized (rhCEAopt) and delivered by sequential DNA electro-gene-transfer (DNA-EGT) and adenoviral (Ad) vector. RhCEAopt was capable to break tolerance to CEA in hCEA transgenic mice and immune responses were detected against epitopes distributed over the entire length of the protein. Xenovaccination with rhCEA resulted in the activation of CD4+ T-cell responses in addition to self-reactive CD8+ T-cells, the development of high-titer antibodies against hCEA, and significant antitumor effects upon challenge with hCEA+ tumor cells. The superior activity of rhCEAopt compared with hCEAopt was confirmed in hCEA/HHD double-transgenic mice, where potent CD8+ T-cell responses against specific human HLA A*0201 hCEA epitopes were detected. Our data show that xenogeneic gene-based vaccination with rhCEA is a viable approach to break tolerance against CEA, thus suggesting further development in the clinical setting.