Although priming with replicating adenovirus type 5 host range mutant (Ad5hr)-human immunodeficiency virus (HIV)/simian immunodeficiency virus (SIV) recombinants, followed by HIV/SIV envelope boosting, has proven highly immunogenic, resulting in protection from SIV/simian-human immunodeficiency virus (SHIV) challenges, Ad5hr recombinant distribution, replication, and persistence have not been examined comprehensively in nonhuman primates. We utilized Ad5hr-green fluorescent protein and Ad5hr-SIV recombinants to track biodistribution and immunogenicity following mucosal priming of rhesus macaques by the intranasal/intratracheal, sublingual, vaginal, or rectal route. Ad recombinants administered by all routes initially targeted macrophages in bronchoalveolar lavage (BAL) fluid and rectal tissue, later extending to myeloid dendritic cells in BAL fluid with persistent expression in rectal mucosa 25 weeks after the last Ad immunization. Comparable SIV-specific immunity, including cellular responses, serum binding antibody, and mucosal secretory IgA, was elicited among all groups. The ability of the vector to replicate in multiple mucosal sites irrespective of delivery route, together with the targeting of macrophages and professional antigen-presenting cells, which provide potent immunogenicity at localized sites of virus entry, warrants continued use of replicating Ad vectors.