Whereas several recent AIDS vaccine strategies have protected rhesus macaques against a pathogenic simian/human immunodeficiency virus (SHIV)_89.6P challenge, similar approaches have provided only modest, transient reductions in viral burden after challenge with virulent, pathogenic SIV, which is more representative of HIV infection of people. We show here that priming with replicating adenovirus recombinants encoding SIV env/rev, gag, and/or nef genes, followed by boosting with SIV gp120 or an SIV polypeptide mimicking the CD4 binding region of the envelope, protects rhesus macaques from intrarectal infection with the highly pathogenic SIV_mac251. Using trend analysis, significant reductions in acute-phase and set point viremia were correlated with anti-gp120 antibody and cellular immune responses, respectively. Within immunization groups exhibiting significant protection, a subset (39%) of macaques have exhibited either no viremia, cleared viremia, or controlled viremia at the threshold of detection, now more than 40 weeks postchallenge. This combination prime-boost strategy, utilizing replication competent adenovirus, is a promising alternative for HIV vaccine development.