CTB-MPR(649-684) is a translational fusion protein consisting of the cholera toxin B subunit and a 36-residue peptide, MPR(649-684), corresponding to the conserved membrane proximal ectodomain of gp41. CTB-MPR(649-684) was previously shown to induce HIV-1 transcytosis-blocking antibodies in mice. In this report, we describe an effective immunization regimen for this novel anti HIV-1 vaccine-candidate. Bacterially-produced CTB-MPR(649-684) was intranasally and/or intraperitoneally administered to investigate several prime-boost heterologous route immunization regimens. Mucosal priming with the adjuvant cholera toxin elicited significant levels of vaginal IgA and serum IgG specific to MPR(649-684). Systemic boosting after mucosal priming enhanced the levels of serum and mucosal antibodies. Systemic priming induced a strong serum anti-MPR(649-684) IgG response, which was efficiently recalled and augmented by either systemic or mucosal boosting. However, this regimen was less effective in inducing secretory anti-MPR(649-684) IgA. The serum anti-MPR(649-684) IgG subtype profile revealed that both IgG1 and IgG2a were induced in all the immunization regimens, and that mucosal co-administration of cholera toxin shifted the bias to the latter subtype. We concluded that, of the various immunization regimens examined here, mucosal priming with adjuvant followed by systemic boosting exhibited the best response in respect to either systemic or mucosal anti-MPR(649-684) antibodies. Most importantly, mucosal antibodies elicited by this regimen significantly inhibited HIV-1 transcytosis in a human tight epithelium model.