The RV144 trial demonstrated that an experimental AIDS vaccine can prevent human immunodeficiency virus type 1 (HIV-1) infection in humans. Because of its limited efficacy, further understanding of the mechanisms of preventive AIDS vaccines remains a priority, and nonhuman primate (NHP) models of lentiviral infection provide an opportunity to define immunogens, vectors, and correlates of immunity. In this study, we show that prime-boost vaccination with a mismatched SIV envelope (Env) gene, derived from simian immunodeficiency virus SIVmac239, prevents infection by SIVsmE660 intrarectally. Analysis of different gene-based prime-boost immunization regimens revealed that recombinant adenovirus type 5 (rAd5) prime followed by replication-defective lymphocytic choriomeningitis virus (rLCMV) boost elicited robust CD4 and CD8 T-cell and humoral immune responses. This vaccine protected against infection after repetitive mucosal challenge with efficacies of 82% per exposure and 62% cumulatively. No effect was seen on viremia in infected vaccinated monkeys compared to controls. Protection correlated with the presence of neutralizing antibodies to the challenge viruses tested in peripheral blood mononuclear cells. These data indicate that a vaccine expressing a mismatched Env gene alone can prevent SIV infection in NHPs and identifies an immune correlate that may guide immunogen selection and immune monitoring for clinical efficacy trials.