The use of adenovirus (Ad) as vaccine vectors is hindered by pre-existing immunity to human Ads in most of the human population. In order to overcome this limitation, uncommon alternative Ad serotypes need to be utilized. In this study, an E1–E3 deleted recombinant Ad based on the chimpanzee serotype 3 (ChAd3) was engineered to express human carcinoembryonic antigen (CEA) protein or rat neu extracellular/transmembrane domains (ECD.TM). ChAd3 vectors were tested in CEA transgenic (CEA.Tg) and BALB/NeuT mice, which show immunologic tolerance to these antigens. ChAd3 is capable of inducing an immune response comparable to that of hAd5 serotype-based vectors, thus breaking tolerance to tumor associated antigens (TAAs) and achieving anti-tumor effects. Of importance is that ChAd3 can overcome hAd5 pre-existing immunity and work in conjunction with DNA electroporation (DNA-EP) and other Ad vaccines based on common human serotypes.