Vaccine-induced cellular immunity controls virus replication in simian immunodeficiency virus (SIV)-infected monkeys only transiently, leading to the question of whether such vaccines for AIDS will be effective. We immunized monkeys with plasmid DNA and replication-defective adenoviral vectors encoding SIV proteins and then challenged them with pathogenic SIV. Although these monkeys demonstrated a reduction in viremia restricted to the early phase of SIV infection, they showed a prolonged survival. This survival was associated with preserved central memory CD4+ T lymphocytes and could be predicted by the magnitude of the vaccine-induced cellular immune response. These immune correlates of vaccine efficacy should guide the evaluation of AIDS vaccines in humans.