The rapid onset of massive, systemic viral replication during primary HIV/SIV infection and the immune evasion capabilities of these viruses pose fundamental problems for vaccines that depend upon initial viral replication to stimulate effector T cell expansion and differentiation1–5. We hypothesized that vaccines designed to maintain differentiated “effector memory” T cell (TEM) responses5,6 at viral entry sites might improve efficacy by impairing viral replication at its earliest stage2, and have therefore developed SIV protein-encoding vectors based on rhesus cytomegalovirus (RhCMV), the prototypical inducer of life-long TEM responses7–9. RhCMV vectors expressing SIV Gag, Rev/Nef/Tat, and Env persistently infected rhesus macaques (RM), regardless of pre-existing RhCMV immunity, and primed and maintained robust SIV-specific, CD4+ and CD8+ TEM responses (characterized by coordinate TNF, IFN-γ and MIP-1β expression, cytotoxic degranulation, and accumulation at extra-lymphoid sites) in the absence of neutralizing antibodies. Compared to control RM, these vaccinated RM showed increased resistance to acquisition of progressive SIVmac239 infection upon repeated, limiting dose, intra-rectal challenge, including four animals that controlled rectal mucosal infection without progressive systemic dissemination. These data suggest a new paradigm for AIDS vaccine development: that vaccines capable of generating and maintaining HIV-specific TEM might decrease the incidence of HIV acquisition after sexual exposure.