Heterologous priming and boosting with antigens expressed by DNA, viral vectors, or as proteins, are experimental strategies to induce strong immune responses against infectious diseases and cancer. In a preclinical study we compared the ability of recombinant modified vaccinia Ankara encoding HIV antigens (MVA-CMDR), and/or recombinant gp140C (rgp140C), to boost responses induced by a multigene/multisubtype HIV DNA vaccine delivered by electroporation (EP). Homologous DNA immunizations augmented by EP stimulated strong cellular immune responses. Still stronger cellular immune responses were observed after DNA priming and MVA-CMDR boosting, which was superior to all other immunization schedules tested in terms of antigen-specific IFN-γ, IL-2, and bifunctional IFN-γ and IL-2 responses. For HIV Env-specific antibody responses, mice receiving repeated rgp140C immunizations, and mice boosted with rgp140C, elicited the highest binding titers and the highest numbers of antibody-secreting B cells. When considering both cellular and humoral immune responses, a combination of DNA, MVA-CMDR, and rgp140C immunizations induced the overall most potent immune responses and the highest avidity of HIV Env-specific antibodies. These data emphasize the importance of including multiple vaccine modalities that can stimulate both T and B cells, and thus elicit strong and balanced immune responses. The present HIV vaccine combination holds promise for further evaluation in clinical trials.