As part of a European initiative (EuroVacc), we report the design, construction, and immunogenicity of two HIV-1 vaccine candidates based on a clade C virus strain (CN54) representing the current major epidemic in Asia and parts of Africa. Open reading frames encoding an artificial 160-kDa GagPolNef (GPN) polyprotein and the external glycoprotein gp120 were fully RNA and codon optimized. A DNA vaccine (DNA-GPN and DNA-gp120, referred to as DNA-C), and a replication-deficient vaccinia virus encoding both reading frames (NYVAC-C), were assessed regarding immunogenicity in Balb/C mice. The intramuscular administration of both plasmid DNA constructs, followed by two booster DNA immunizations, induced substantial T-cell responses against both antigens as well as Env-specific antibodies. Whereas low doses of NYVAC-C failed to induce specific CTL or antibodies, high doses generated cellular as well as humoral immune responses, but these did not reach the levels seen following DNA vaccination. The most potent immune responses were detectable using prime:boost protocols, regardless of whether DNA-C or NYVAC-C was used as the priming or boosting agent. These preclinical findings revealed the immunogenic response triggered by DNA-C and its enhancement by combining it with NYVAC-C, thus complementing the macaque preclinical and human phase I clinical studies of EuroVacc.