This study analyzed a heterologous prime-boost vaccine approach against HIV-1 using three different antigenically unrelated negative-stranded viruses (NSV) expressing HIV-1 Gag as vaccine vectors: rabies virus (RABV), vesicular stomatitis virus (VSV) and Newcastle disease virus (NDV). We hypothesized that this approach would result in more robust cellular immune responses than those achieved with the use of any of the vaccines alone in a homologous prime-boost regimen. To this end, we primed BALB/c mice with each of the NSV-based vectors. Primed mice were rested for thirty-five days after which we administered a second immunization with the same or heterologous NSV-Gag viruses. The magnitude and quality of the Gag-specific CD8(+) T cells in response to these vectors post boost were measured. In addition, we performed challenge experiments using vaccinia virus expressing HIV-1 Gag (VV-Gag) thirty-three days after the boost inoculation. Our results showed that the choice of the vaccine used for priming was important for the detected Gag-specific CD8(+) T cell recall responses post boost and that NDV-Gag appeared to result in a more robust recall of CD8(+) T cell responses independent of the prime vaccine used. However, the different prime-boost strategies were not distinct for the parameters studied in the challenge experiments using VV-Gag but did indicate some benefits compared to single immunizations. Taken together, our data show that NSV vectors can individually stimulate HIV-Gag specific CD8(+) T cells that are effectively recalled by other NSV vectors in a heterologous prime-boost approach. These results provide evidence that RABV, VSV and NDV can be used in combination to develop vaccines needing prime-boost regimens to stimulate effective immune responses.