Showing modest efficacy, the RV144 HIV-1 vaccine clinical trial utilized a non-replicating canarypox viral vector and a soluble gp120 protein boost. Here we built upon the RV144 strategy by developing a novel combination of a replicating, but highly-attenuated Vaccinia virus vector, NYVAC-KC, and plant-produced HIV-1 virus-like particles (VLPs). Both components contained the full-length Gag and a membrane anchored truncated gp41 presenting the membrane proximal external region with its conserved broadly neutralizing epitopes in the pre-fusion conformation. We tested different prime/boost combinations of these components in mice and showed that the group primed with NYVAC-KC and boosted with both the viral vectors and plant-produced VLPs have the most robust Gag-specific CD8 T cell responses, at 12.7% of CD8 T cells expressing IFN-γ in response to stimulation with five Gag epitopes. The same immunization group elicited the best systemic and mucosal antibody responses to Gag and dgp41 with a bias towards IgG1.