Although no sufficiently efficacious HIV vaccine exists so far, research is very active to develop prime-boost strategies combining series of two different vaccine candidates in a sequential manner. In order to identify promising strategies, we investigated whether the order of administration of the vaccine candidates within such prime-boost strategies impacts the induced immune responses. We used three different vaccine candidates (MVA HIV-B, HIV LIPO-5 and DNA GTU-MultiHIV B) in four prime-boost strategies and evaluated the immune responses to these strategies in a randomized clinical trial with 92 healthy adult volunteers, focussing our assessments on T-cell responses and gene expression induced by the vaccines. We found that the MVA HIV-B vaccine candidate induced a spectrum of T-cell responses, in particular when it was administered after the DNA GTU-MultiHIV B vaccine. We further identified a gene expression signature in the blood, which was specific to the MVA HIV-B vaccine, regardless of whether it was given as the first vaccine series (prime) or as the second one (boost). These findings provide new insights into the immune effects of different HIV vaccine candidates and more specifically of the MVA HIV-B vaccine.