Recombinant adenoviral vectors (rAds) are the most potent recombinant vaccines for eliciting CD8+; T cell-mediated immunity in humans; however, prior exposure from natural adenoviral infection can decrease such responses. In this study we show low seroreactivity in humans against simian- (sAd11, sAd16) or chimpanzee-derived (chAd3, chAd63) compared with human-derived (rAd5, rAd28, rAd35) vectors across multiple geographic regions. We then compared the magnitude, quality, phenotype, and protective capacity of CD8 +; T cell responses in mice vaccinated with rAds encoding SIV Gag. Using a dose range (1 3 107-109 particle units), we defined a hierarchy among rAd vectors based on the magnitude and protective capacity of CD8+; T cell responses, from most to least, as: rAd5 and chAd3, rAd28 and sAd11, chAd63, sAd16, and rAd35. Selection of rAd vector or dose could modulate the proportion and/or frequency of IFN-γ+;TNF- α+;IL-2+; and KLRG1+;CD1272CD8 +; T cells, but strikingly ∼30-80% of memory CD8+; T cells coexpressed CD127 and KLRG1. To further optimize CD8+; T cell responses, we assessed rAds as part of prime-boost regimens. Mice primed with rAds and boosted with NYVAC generated Gag-specific responses that approached ∼60% of total CD8+; T cells at peak. Alternatively, priming with DNA or rAd28 and boosting with rAd5 or chAd3 induced robust and equivalent CD8+; T cell responses compared with prime or boost alone. Collectively, these data provide the immunologic basis for using specific rAd vectors alone or as part of prime-boost regimens to induce CD8+; T cells for rapid effector function or robust long-term memory, respectively.