We have shown that sequential replicating adenovirus type 5 host range mutant human immunodeficiency virus/simian immunodeficiency virus (HIV/SIV) recombinant priming delivered first intranasally (i.n.) plus orally and then intratracheally (i.t.), followed by envelope protein boosting, elicits broad cellular immunity and functional, envelope-specific serum and mucosal antibodies that correlate with protection from high-dose SIV and simian/human immunodeficiency virus (SHIV) challenges in rhesus macaques. Here we extended these studies to compare the standard i.n./i.t. regimen with additional mucosal administration routes, including sublingual, rectal, and vaginal routes. Similar systemic cellular and humoral immunity was elicited by all immunization routes. Central and effector memory T cell responses were also elicited by the four immunization routes in bronchoalveolar lavage fluid and jejunal, rectal, and vaginal tissue samples. Cellular responses in vaginal tissue were more compartmentalized, being induced primarily by intravaginal administration. In contrast, all immunization routes elicited secretory IgA (sIgA) responses at multiple mucosal sites. Following a repeated low-dose intrarectal (i.r.) challenge with SIV(mac251) at a dose transmitting one or two variants, protection against acquisition was not achieved except in one macaque in the i.r. immunized group. All immunized macaques exhibited reduced peak viremia compared to that of controls, correlated inversely with prechallenge serum antienvelope avidity, antibody-dependent cellular cytotoxicity (ADCC) titers, and percent antibody-dependent cell-mediated viral inhibition. Both antibody avidity and ADCC titers were correlated with the number of exposures required for infection. Notably, we show for the first time a significant correlation of vaccine-induced sIgA titers in rectal secretions with delayed acquisition. Further investigation of the characteristics and properties of the sIgA should elucidate the mechanism leading to this protective effect.