Heterologous prime boost with DNA and recombinant modified vaccinia virus Ankara (rMVA) vaccines is considered as a promising vaccination approach against human immunodeficiency virus (HIV-1). To further enhance the efficacy of DNA-rMVA vaccination, we investigated humoral and cellular immune responses in mice after three sequential immunizations with DNA, a combination of DNA and virus-like particles (VLP), and rMVA expressing HIV-1 89.6 gp120 envelope proteins (Env). DNA prime and boost with a combination of VLP and DNA vaccines followed by an rMVA boost induced over a 100-fold increase in Env-specific IgG antibody titers compared to three sequential immunizations with DNA and rMVA. Cellular immune responses were induced by VLP-DNA and rMVA vaccinations at high levels in CD8 T cells, CD4 T cells, and peripheral blood mononuclear cells secreting interferon (IFN)-γ, and spleen cells producing interleukin (IL)-2, 4, 5 cytokines. This study suggests that a DNA and VLP combination vaccine with MVA is a promising strategy in enhancing the efficacy of DNA-rMVA vaccination against HIV-1.