Vectors encoding CEA fused to the A (CEA-LTA) or B (CEA-LTB) subunits of the heat-labile enterotoxin were constructed and their immunogenicity was compared. The CEA-LTB fusion was shown to elicit a greater CEA-specific antibody and CD8+ T-cell response. Plasmid DNA and Adenovirus vectors encoding CEA-LTB proved to be immunogenic in CEA transgenic (CEA.tg) mice. CEA.tg mice immunized with repeated injections of plasmid pV1J/CEA-LTB followed by Ad/CEA-LTB were protected from tumor growth, but the adjuvant activity of the LTB protein was lost upon mutation of the LTB sequence. Depletion of T-regulatory cells increased the vaccine antitumor effect. Tumor protection was abrogated if the NK or CD8+ cell population was depleted before tumor challenge. Passive transfer studies demonstrated that CD8+ T cells contribute to the antitumor effect, thus suggesting that a genetic vaccine based on plasmid DNA and adenoviral vectors encoding CEA-LTB augments CEA-specific immune responses and significantly protects from tumor development.