Adenovirus vectors are widely used as vaccine candidates for a variety of pathogens, including HIV-1. To date, human and chimpanzee adenoviruses have been explored in detail as vaccine vectors. The phylogeny of human and chimpanzee adenoviruses is overlapping, and preexisting humoral and cellular immunity to both are exhibited in human populations worldwide. More distantly related adenoviruses may therefore offer advantages as vaccine vectors. Here we describe the primary isolation and vectorization of three novel adenoviruses from rhesus monkeys. The seroprevalence of these novel rhesus monkey adenovirus vectors was extremely low in sub-Saharan Africa human populations, and these vectors proved to have immunogenicity comparable to that of human and chimpanzee adenovirus vaccine vectors in mice. These rhesus monkey adenoviruses phylogenetically clustered with the poorly described adenovirus species G and robustly stimulated innate immune responses. These novel adenoviruses represent a new class of candidate vaccine vectors.