To identify the protective mechanisms of an HIV mucosal vaccine similar to RV144, we carried out a pilot study in which we mucosally immunized rhesus macaques with HIV/SIV peptides, SIV-expressing MVA, and full-length single chain protein of HIV-gp120 fused to CD4. In the macaques that received this combination, 3/14 were sterilely protected after high-dose SHIVSF162P4 intrarectal challenge, compared to 0/29 controls (p = 0.03). We observed mucosal antigen-specific T cell responses, but not antibody responses. We then tested efficacy of this HIV mucosal vaccine against repeated low-dose intrarectal challenge with SHIVSF162P4. With 21 vaccinees and 7 controls, we achieved 44% vaccine efficacy (p = 0.028). Consistent with the pilot study, the vaccine did not induce Env-specific antibody responses in the plasma or rectal mucosa. It induced gag- and Env-specific T cells in colorectal mucosa/MLN, but the magnitude did not correlate with delay of viral acquisition. Interestingly, the vaccine led to accumulation of myeloid-derived suppressor cells in the PBMCs and CD14+ monocytes in the colorectal intraepithelial compartment, which correlated with delay of viral acquisition. The vaccine also decreased rectal gp41 antibody, total rectal mucosal plasma cells, and gut microbiome richness. The bacterial PCA-1 correlated with number of exposures to achieve infection, suggesting gut microbiome's possibly influencing HIV susceptibility. Overall, the mucosal vaccine had different protective mechanisms from the RV144 trial. Thus, a vaccine inducing mucosal T cells without antibodies can protect against mucosal SHIV acquisition. Combination with a systemically-delivered antibody-inducing vaccine might improve protection.