The acquired immunodeficiency syndrome (AIDS)-causing lentiviruses human immunodeficiency virus (HIV) and simian immunodeficiency virus (SIV) effectively evade host immunity and, once established, infections with these viruses are only rarely controlled by immunological mechanisms. However, the initial establishment of infection in the first few days after mucosal exposure, before viral dissemination and massive replication, may be more vulnerable to immune control. Here we report that SIV vaccines that include rhesus cytomegalovirus (RhCMV) vectors establish indefinitely persistent, high-frequency, SIV-specific effector memory T-cell (T(EM)) responses at potential sites of SIV replication in rhesus macaques and stringently control highly pathogenic SIV(MAC239) infection early after mucosal challenge. Thirteen of twenty-four rhesus macaques receiving either RhCMV vectors alone or RhCMV vectors followed by adenovirus 5 (Ad5) vectors (versus 0 of 9 DNA/Ad5-vaccinated rhesus macaques) manifested early complete control of SIV (undetectable plasma virus), and in twelve of these thirteen animals we observed long-term (≥1 year) protection. This was characterized by: occasional blips of plasma viraemia that ultimately waned; predominantly undetectable cell-associated viral load in blood and lymph node mononuclear cells; no depletion of effector-site CD4(+) memory T cells; no induction or boosting of SIV Env-specific antibodies; and induction and then loss of T-cell responses to an SIV protein (Vif) not included in the RhCMV vectors. Protection correlated with the magnitude of the peak SIV-specific CD8(+) T-cell responses in the vaccine phase, and occurred without anamnestic T-cell responses. Remarkably, long-term RhCMV vector-associated SIV control was insensitive to either CD8(+) or CD4(+) lymphocyte depletion and, at necropsy, cell-associated SIV was only occasionally measurable at the limit of detection with ultrasensitive assays, observations that indicate the possibility of eventual viral clearance. Thus, persistent vectors such as CMV and their associated T(EM) responses might significantly contribute to an efficacious HIV/AIDS vaccine.