The HIV vaccine strategy that, to date, generated immune protection consisted of a prime-boost regimen using a canarypox vector and an HIV envelope protein with alum, as shown in the RV144 trial. Since the efficacy was weak, and previous HIV vaccine trials designed to generate antibody responses failed, we hypothesized that generation of T cell responses would result in improved protection. Thus, we tested the immunogenicity of a similar envelope-based vaccine using a mouse model, with two modifications: a clade C CN54gp140 HIV envelope protein was adjuvanted by the TLR9 agonist IC31®, and the viral vector was the vaccinia strain NYVAC-CN54 expressing HIV envelope gp120. The use of IC31® facilitated immunoglobulin isotype switching, leading to the production of Env-specific IgG2a, as compared to protein with alum alone. Boosting with NYVAC-CN54 resulted in the generation of more robust Th1 T cell responses. Moreover, gp140 prime with IC31® and alum followed by NYVAC-CN54 boost resulted in the formation and persistence of central and effector memory populations in the spleen and an effector memory population in the gut. Our data suggest that this regimen is promising and could improve the protection rate by eliciting strong and long-lasting humoral and cellular immune responses.