All human immunodeficiency virus (HIV) vaccine efficacy trials to date have ended in failure. Structural features of the Env glycoprotein and its enormous variability have frustrated efforts to induce broadly reactive neutralizing antibodies. To explore the extent to which vaccine-induced cellular immune responses, in the absence of neutralizing antibodies, can control replication of a heterologous, mucosal viral challenge, we vaccinated eight macaques with a DNA/Ad5 regimen expressing all of the proteins of SIVmac239 except Env. Vaccinees mounted high-frequency T-cell responses against 11 to 34 epitopes. We challenged the vaccinees and eight naïve animals with the heterologous biological isolate SIVsmE660, using a regimen intended to mimic typical HIV exposures resulting in infection. Viral loads in the vaccinees were significantly less at both the peak (1.9-log reduction; P < 0.03) and at the set point (2.6-log reduction; P < 0.006) than those in control naïve animals. Five of eight vaccinated macaques controlled acute peak viral replication to less than 80,000 viral RNA (vRNA) copy eq/ml and to less than 100 vRNA copy eq/ml in the chronic phase. Our results demonstrate that broad vaccine-induced cellular immune responses can effectively control replication of a pathogenic, heterologous AIDS virus, suggesting that T-cell-based vaccines may have greater potential than previously appreciated.