In animal models, E1-deleted human adenoviral recombinants of the serotype 5 (AdHu5) have shown high efficacy as vaccine carriers for different Ags including those of HIV-1. Humans are infected by common serotypes of human adenovirus such as AdHu5 early in life and a significant percentage has high levels of neutralizing Abs to these serotypes, which will very likely impair the efficacy of recombinant vaccines based on the homologous virus. To circumvent this problem, a novel replication-defective adenoviral vaccine carrier based on an E1-deleted recombinant of the chimpanzee adenovirus 68 (AdC68) was developed. An AdC68 construct expressing a codon-optimized, truncated form of gag of HIV-1 induces CD8(+) T cells to gag in mice which at the height of the immune response encompass nearly 20% of the entire splenic CD8(+) T cell population. The vaccine-induced immune response provides protection to challenge with a vaccinia gag recombinant virus. Induction of transgene-specific CD8(+) T cells and protection against viral challenge elicited by the AdC68 vaccines is not strongly inhibited in animals preimmune to AdHu5 virus. However, the response elicited by the AdHu5 vaccine is greatly attenuated in AdHu5 preimmune animals.