T cell-mediated immune responses play an important role in the containment of HIV-1 replication. Therefore, an effective vaccine against HIV-1 should be able to elicit high frequencies of virus-specific CD8+ and CD4+ T cells. The highly attenuated poxvirus-based vaccine candidate, NYVAC-SIV-gag-pol-env (NYVAC-SIV-gpe), has been shown to induce and/or expand SIV-specific CD4+ and CD8+ T cell responses in both naive and infected macaques. In this study, the immunogenicity of NYVAC-SIV-gpe alone was compared with a combination regimen where priming with an optimized DNA-SIV-gag-env vaccine candidate was followed by a NYVAC-SIV-gpe boost. In macaques immunized with the prime-boost regimen, the extent and durability of CD8+ T cell response to an immunodominant SIV gag epitope was increased and these animals recognized a broader array of sub-dominant SIV epitopes in the cytolytic assay. In addition, the prime-boost regimen significantly enhanced the proliferative responses to both SIV gag and env proteins. Thus, the combination of these vaccine modalities may represent a valuable strategy in the development of a vaccine for HIV.