Immunization schemes employing priming with vector-based vaccine candidates followed by subunit booster administrations have been explored and shown to have merit in the human immunodeficiency virus type 1 (HIV-1) and simian immunodeficiency virus systems. In this study, we have assessed the priming capacity of highly attenuated poxvirus vector (NYVAC and ALVAC)-based HIV-2 recombinants, as well as Salmonella typhimurium HIV-2 recombinants in rhesus macaques. ALVAC- and NYVAC-based vaccine candidates expressing the HIV-2 gag, pol, and env genes or NYVAC-based recombinants expressing either gp160 or gp120 were used to immunize rhesus macaques in combination protocols with alum-adjuvanted HIV-2 rgp160. Following intravenous challenge exposure with 100 infectious doses of the HIV-2SBL6669 parental virus genotype mixture, seven of eight animals were protected from infection. The seven protected animals were rechallenged 6 months postprimary challenge, without additional booster inoculations, with the same dose of the HIV-2SBL6669 parental virus. Five of the seven animals remained protected against HIV-2 infection at 6 months following the second challenge. In contrast, oral immunization with recombinant Salmonella expressing the HIV-2 gag and the gp120 portion of the envelope either alone or in combination with alum-adjuvanted rgp160 failed to confer protection. These results suggest that the NYVAC- and ALVAC-based recombinants may confer long-lasting protection and that these two highly attenuated poxvirus vaccine vectors may represent promising candidates for developing an acquired immunodeficiency syndrome vaccine.