The aim of this randomised controlled trial was to see if the addition of 4 mg/ml DNA-C priming given by the intramuscular route at weeks 0 and 4 to NYVAC-C at weeks 20 and 24, safely increased the proportion of participants with HIV-specific T-cell responses measured by the interferon (IFN)-gamma ELISpot assay at weeks 26 and/or 28 compared to NYVAC-C alone. Although 2 individuals discontinued after the first DNA-C due to adverse events (1 vaso-vagal; 1 transient, asymptomatic elevation in alanine transaminase), the vaccines were well tolerated. Three others failed to complete the regimen (1 changed her mind; 2 lost to follow-up). Of the 35 that completed the regimen 90% (18/20) in the DNA-C group had ELISpot responses compared to 33% (5/15) that received NYVAC-C alone (p=0.001). Responses were to envelope in the majority (21/23). Of the 9 individuals with responses to envelope and other peptides, 8 were in the DNA-C group. These promising results suggest that DNA-C was an effective priming agent, that merits further investigation.