We evaluated four priming-boosting vaccine regimens for the highly pathogenic simian human immunodeficiency virus SHIV89.6P in Macaca nemestrina. Each regimen included gene gun delivery of a DNA vaccine expressing all SHIV89.6 genes plus Env gp160 of SHIV89.6P. Additional components were two recombinant vaccinia viruses, expressing SHIV89.6 Gag-Pol or Env gp160, and inactivated SHIV89.6 virus. We compared (i) DNA priming/DNA boosting, (ii) DNA priming/inactivated virus boosting, (iii) DNA priming/vaccinia virus boosting, and (iv) vaccinia virus priming/DNA boosting versus sham vaccines in groups of 6 macaques. Prechallenge antibody responses to Env and Gag were strongest in the groups that received vaccinia virus priming or boosting. Cellular immunity to SHIV89.6 peptides was measured by enzyme-linked immunospot assay; strong responses to Gag and Env were found in 9 of 12 vaccinia virus vaccinees and 1 of 6 DNA-primed/inactivated-virus-boosted animals. Vaccinated macaques were challenged intrarectally with 50 50% animal infectious doses of SHIV89.6P 3 weeks after the last immunization. All animals became infected. Five of six DNA-vaccinated and 5 of 6 DNA-primed/particle-boosted animals, as well as all 6 controls, experienced severe CD4(+)-T-cell loss in the first 3 weeks after infection. In contrast, DNA priming/vaccinia virus boosting and vaccinia virus priming/DNA boosting vaccines both protected animals from disease: 11 of 12 macaques had no loss of CD4(+) T cells or moderate declines. Virus loads in plasma at the set point were significantly lower in vaccinia virus-primed/DNA-boosted animals versus controls (P = 0.03). We conclude that multigene vaccines delivered by a combination of vaccinia virus and gene gun-delivered DNA were effective against SHIV89.6P viral challenge in M. nemestrina.