Replication-defective adenovirus vectors based on human serotype 5 (Ad5) induce protective immune responses against diverse pathogens and cancer in animal models, as well as elicit robust and sustained cellular immunity in humans. However, most humans have neutralizing antibodies to Ad5, which can impair the immunological potency of such vaccines. Here, we show that rare serotypes of human adenoviruses, which should not be neutralized in most humans, are far less potent as vaccine vectors than Ad5 in mice and nonhuman primates, casting doubt on their potential efficacy in humans. To identify novel vaccine carriers suitable for vaccine delivery in humans, we isolated and sequenced more than 1000 adenovirus strains from chimpanzees (ChAd). Replication-defective vectors were generated from a subset of these ChAd serotypes and screened to determine whether they were neutralized by human sera and able to grow in human cell lines. We then ranked these ChAd vectors by immunological potency and found up to a thousandfold variation in potency for CD8+ T cell induction in mice. These ChAd vectors were safe and immunologically potent in phase 1 clinical trials, thereby validating our screening approach. These data suggest that the ChAd vectors developed here represent a large collection of non-cross-reactive, potent vectors that may be exploited for the development of new vaccines.