Gastrointestinal and vaginal mucosa are major sites of entry in natural HIV infection and therefore the preferred sites to elicit high-avidity CD8⁺ CTL by vaccination. We directly compare systemic and mucosal immunization in mice after DNA priming and boosting with rgp160 env expressed either in MVA or Ad for their ability to induce mucosal as well as systemic HIV-specific CTL. The optimal CTL response in the gut mucosa was observed after priming with the HIV-1 gp160 env DNA vaccine and boosting with rMVA or rAd encoding the same envelope gene all administered intrarectally (IR). Maximum levels of high-avidity CD8⁺ T cells were seen in intestinal lamina propria following this regimen. When the prime and boost routes were distinct, the delivery site of the boost had a greater impact than the DNA priming. IM DNA prime and IR rMVA boost were more effective than IR DNA prime and IM rMVA boost for eliciting mucosal CD8⁺ T-cell avidity. A systemic DNA-prime-followed by systemic rMVA boost induced high levels of high-avidity CD8⁺ T cells systemically, but responses were undetectable in mucosal sites. A single systemic immunization with rMVA was sufficient to induce high-avidity IFN-γ secreting CD8⁺ T cells in systemic organs, whereas a single mucosal immunization with rMVA was not sufficient to elicit high-avidity CD8⁺ T cells in mucosa. Thus, a heterologous mucosal DNA prime-viral vectored boost strategy was needed. The requirement for a heterologous DNA prime-recombinant viral boost strategy for generation of high-avidity CD8⁺ T cells in mucosal sites in mice may be more stringent than for the induction of high-avidity CD8⁺ T cells in systemic compartments.