We evaluated replication-defective poxvirus vectors (modified vaccinia Ankara [MVA] and fowlpox [FPV]) in a homologous and heterologous vector prime-boost vaccination regimen containing matching HIV inserts (MVA-HIV and FPV-HIV) given at months 0, 1, 3, 5 and 7 in 150 healthy HIV-negative vaccinia-naïve participants. FPV-HIV alone was poorly immunogenic, while the high dose (109pfu/2ml) of MVA-HIV alone elicited maximal responses after two injections: CD4+ and CD8+ T-cell responses in 26/55 (47.3%) and 5/60 (8.3%) of participants, respectively and IFN-γ ELISpot responses in 28/62 (45.2%). The infrequent CD8+ T-cell responses following MVA-HIV priming were boosted only by the heterologous (FPV-HIV) construct in 14/27 [51.9%] of participants post-4th vaccination. Alternatively, HIV envelope-specific binding antibodies were demonstrated in approximately two-thirds of recipients of the homologous boosting regimen, but in less than 20% of subjects after the heterologous vector boost. Thus, a heterologous poxvirus vector prime-boost regimen can induce an HIV-specific CD8+ T-cell and CD4+ T-cell responses, which may be an important feature of an optimal regimen for preventive HIV vaccination.