Most HIV-1 infections are thought to occur at mucosal surfaces during sexual contact. It has been hypothesized that vaccines delivered at mucosal surfaces may mediate better protection against HIV-1 than vaccines that are delivered systemically. To test this, rhesus macaques were vaccinated by intramuscular (i.m.) or intravaginal (ivag.) routes with helper-dependent adenoviral (HD-Ad) vectors expressing HIV-1 envelope. Macaques were first immunized intranasally with species C Ad serotype 5 (Ad5) prior to serotype-switching with species C HD-Ad6, Ad1, Ad5, and Ad2 vectors expressing env followed by rectal challenge with CCR5-tropic SHIV-SF162P3. Vaccination by the systemic route generated stronger systemic CD8 T cell responses in PBMC, but weaker mucosal responses. Conversely, mucosal immunization generated stronger CD4 T cell central memory (Tcm) responses in the colon. Intramuscular immunization generated higher levels of env-binding antibodies, but neither produced neutralizing or cytotoxic antibodies. After mucosal SHIV challenge, both groups controlled SHIV better than control animals. However, more animals in the ivag. group had lower viral set points than in in the i.m. group. These data suggest mucosal vaccination may have improve protection against sexually-transmitted HIV. These data also demonstrate that helper-dependent Ad vaccines can mediate robust vaccine responses in the face of prior immunity to Ad5 and during four rounds of adenovirus vaccination.