Mucosal surfaces are not targeted by most human immunodeficiency virus type 1 (HIV-1) vaccines, despite being major routes for HIV-1 transmission. Here we report a novel vaccination regimen consisting of a mucosal prime with a modified replicating vaccinia virus Tiantan strain (MVTT(SIVgpe)) and an intramuscular boost with a nonreplicating adenovirus strain (Ad5(SIVgpe)). This regimen elicited robust cellular immune responses with enhanced magnitudes, sustainability, and polyfunctionality, as well as higher titers of neutralizing antibodies against the simian immunodeficiency virus SIV(mac1A11) in rhesus monkeys. The reductions in peak and set-point viral loads were significant in most animals, with one other animal being protected fully from high-dose intrarectal inoculation of SIV(mac239). Furthermore, the animals vaccinated with this regimen were healthy, while ~75% of control animals developed simian AIDS. The protective effects correlated with the vaccine-elicited SIV-specific CD8(+) T cell responses against Gag and Pol. Our study provides a novel strategy for developing an HIV-1 vaccine by using the combination of a replicating vector and mucosal priming.