We assessed four prime-boost vaccine regimens with a Gene Gun component for SHIV89.6P in Macaca nemestrina. A dosing experiment using beta-galactosidase plasmid showed that 30 or 45 shots per dose elicited higher titer antibody than smaller doses. For SHIV89.6P, we administered a six-plasmid vaccine capable of producing non-infectious virions in vivo in combination with either vaccinia recombinants or inactivated virus. DNA prime/vaccinia boost, or the reverse, elicited strong immune responses. The SHIV89.6P challenge virus was grown in M. nemestrina peripheral blood mononuclear cells and titered in vivo intrarectally. As has been observed for SHIV89.6P in M. mulatta, the infected M. nemestrina experienced rapid and severe loss of circulating CD4+ T cells. Vaccinated macaques were challenged three weeks after the last boost. DNA prime/vaccina boost or vaccina prime/DNA boost protected 11/12 animals from acute CD4+ T cell depletion and disease, while other regimens were not effective.