Mucosal tissues are major sites of HIV entry and initial infection. Thus, the induction of a mucosal cytotoxic T lymphocyte (CTL) response is an important feature for an effective HIV vaccine. However, little is known about approaches to induce such a protective CTL response in the mucosa. Here for the first time we show that intrarectal immunization with a synthetic, multideterminant HIV peptide plus cholera toxin adjuvant induced long-lasting, antigen-specific CTL memory in both the inductive (Peyer’s patch) and effector (lamina propria) mucosal sites, as well as in systemic sites (spleen), whereas systemic immunization induced specific CTL only in the spleen. Cholera toxin adjuvant, while enhancing the response, was not essential. The CTL recognized target cells either pulsed with HIV peptide or expressing endogenous whole envelope glycoprotein of M_r 160,000 (gp160). Exploring the requirements for CTL induction, we show that mucosal CTL responses are both interleukin 12 and interferon-γ dependent by using antibody-treated and knock-out mice. Finally, to determine whether a mucosal response is actually protective against local mucosal challenge with virus, we show that intrarectal immunization with the synthetic HIV peptide vaccine protected mice against infection via mucosal challenge with a recombinant vaccinia virus expressing HIV-1IIIB gp160. These studies provide an approach to development of an HIV vaccine that induces CTL immunity in the mucosal and systemic immune systems and protects against mucosal infection with a virus expressing HIV-1 gp160.