Most HIV infections result from heterosexual transmission to women. Because cellular immunity plays a key role in the control of the infection, we sought to strengthen cellular immune responses in vaginal tissue. We explored a novel prime-boost protocol that used two live mucosal agents that trigger different pathways of innate immunity and induce strong cellular immunity. Adenovirus serotype 5 (Ad5) has frequently been used as a boost for DNA vaccines. In this study we used attenuated, recombinant L. monocytogenes-gag (rLm-gag) to prime mice by various mucosal routes-oral, intrarectal, and intravaginally (ivag)-followed by a systemic or mucosal boost with replication-defective rAd5-gag. Mice primed with a single administration of rLm-gag by any route and then boosted with rAd5-gag intramuscularly exhibited abundant Gag-specific CD8 T cells in spleen and vaginal lamina propria. Conversely, when boosted with rAd5-gag ivag, the immune response was reoriented toward the vagina with strikingly higher CD8 T cell responses in that tissue, particularly after ivag immunization by both vectors (ivag/ivag). Five weeks to 5 mo later, ivag/ivag-immunized mice continued to show high levels of effector memory CD8 T cells in vagina, while the pool of memory T cells in spleen assumed a progressively more central memory T cell phenotype. The memory mice showed high in vivo CTL activity in vagina, a strong recall response, and robust protection after ivag vaccinia-gag challenge, suggesting that this prime-boost strategy can induce strong cellular immunity, especially in vaginal tissues, and might be able to block the heterosexual transmission of HIV-1 at the vaginal mucosa.