Further advances are required in understanding protection from AIDS by T cell immunity across mucosal sites of virus transmission. We analysed a set of multigenic HIV and SHIV DNA and Fowlpoxvirus (FPV) prime and boost vaccines for immunogenicity and protective efficacy in outbred pigtail macaques when delivered via mucosal surfaces (intranasally or intrarectally). Intranasally delivered DNA, even when adjuvanted and given as a fine droplet spray, was neither immunogenic nor protective in macaques. Some protection from acute infection with a pathogenic vaginal SHIVSF162P3 challenge was, however, observed with a regimen involving intramuscular DNA vaccine priming followed by either intranasally or intrarectally delivered rFPV boosting. Interestingly, animals boosted with rFPV vaccine via either of these mucosal routes had poor circulating T cell responses prior to challenge with SHIV compared to those boosted via the intramuscular route. Nevertheless, the mucosally-vaccinated animals generated equivalent anamnestic mucosal and systemic SHIV-specific CD4 and CD8 T cell responses following SHIV administration, with significant reduction in acute plasma viremia against this vaginal challenge. Our data suggest strategies for effective priming of partial immunity to mucosal HIV-1 exposure utilizing systemic prime and mucosal boost vaccination strategies.