The rising global HIV-1 burden urgently requires vaccines capable of providing heterologous protection. Here, we developed a clade C HIV-1 vaccine consisting of priming with modified vaccinia Ankara (MVA) and boosting with cyclically permuted trimeric gp120 (CycP-gp120) protein, delivered either orally using a needle-free injector or through parenteral injection. We tested protective efficacy of the vaccine against intrarectal challenges with a pathogenic heterologous clade C SHIV infection in rhesus macaques. Both routes of vaccination induced a strong envelope-specific IgG in serum and rectal secretions directed against V1V2 scaffolds from a global panel of viruses with polyfunctional activities. Envelope-specific IgG showed lower fucosylation compared with total IgG at baseline, and most of the vaccine-induced proliferating blood CD4+ T cells did not express CCR5 and α4β7, markers associated with HIV target cells. After SHIV challenge, both routes of vaccination conferred significant and equivalent protection, with 40% of animals remaining uninfected at the end of six weekly repeated challenges with an estimated efficacy of 68% per exposure. Induction of envelope-specific IgG correlated positively with G1FB glycosylation, and G2S2F glycosylation correlated negatively with protection. Vaccine-induced TNF-α+ IFN-γ+ CD8+ T cells and TNF-α+ CD4+ T cells expressing low levels of CCR5 in the rectum at prechallenge were associated with decreased risk of SHIV acquisition. These results demonstrate that the clade C MVA/CycP-gp120 vaccine provides heterologous protection against a tier2 SHIV rectal challenge by inducing a polyfunctional antibody response with distinct Fc glycosylation profile, as well as cytotoxic CD8 T cell response and CCR5-negative T helper response in the rectum.