A recombinant Newcastle disease virus (rNDV) expressing simian immunodeficiency virus (SIV) Gag protein (rNDV/SIVgag) was generated. The rNDV/SIVgag virus induced Gag-specific cellular immune responses in mice, leading to a specific anti-Gag antiviral immunity. This was evidenced by the inhibition of growth of recombinant vaccinia virus expressing an identical Gag antigen (rVac/SIVgag) but not of wild-type vaccinia virus in rNDV/SIVgag-immunized mice. Among intravenous, intraperitoneal, or intranasal immunization routes, intranasal administration induced the strongest protective response against challenge with rVac/SIVgag. We further demonstrated that these immune responses were greatly enhanced after booster immunization with recombinant influenza viruses expressing immunogenic portions of SIV Gag. The magnitude of the protective immune response correlated with the levels of cellular immune responses to Gag, which were still evident 9 weeks after immunization. These results suggest that rNDV and influenza virus vectors are suitable candidate vaccines against AIDS as well as against other infectious diseases.