Viral vectors are considered as one of the major means for the induction of strong immune responses against recombinant antigens by genetic immunization. Among these, lentiviral vectors are particularly attractive vehicles, as they can infect a wide variety of cells and can transduce replicating as well as non-replicating cells. We have engineered VRX1023, an HIV-1-based lentiviral vector (LV) vaccine candidate, to deliver HIV-1 Gag, Pol and Rev antigens under control of the native LTR promoter. While VRX1023 has been shown to elicit strong cell-mediated and humoral immunity as a stand-alone vaccine, we report here its combination in a heterologous prime-boost approach. Its combination with an adenovirus serotype 5 (Ad5)-based vector in the mouse model increased the frequency and polyfunctionality of HIV-specific CD4+ and CD8+ T cells. Homologous prime-boost regimens induced high levels of anti-vector neutralizing antibodies in Ad5-immunized mice, whereas the VSV-G-pseudotyped VRX1023 LV elicited low levels of anti-lentiviral vector neutralization. In addition, the heterologous prime-boost strategy resulted in a 5-fold reduction in Ad5-specific vector neutralization as compared to Ad5 homologous immunization. In conclusion, this study demonstrates that LV and Ad5 vector candidates can be combined in a heterologous immunization regimen, yielding dramatically improved immunogenicity while overcoming anti-vector immunity. These findings may have implications for the development of HIV vaccine regimens in populations with elevated Ad5 seroprevalence or when repeated vector administrations are required.