H56:IC31 is a candidate tuberculosis vaccine comprising a fusion protein of Ag85B, ESAT-6 and Rv2660c, formulated in IC31 adjuvant. This first-in-human, open label phase I trial assessed the safety and immunogenicity of H56:IC31 in healthy adults without or with Mycobacterium tuberculosis (M.tb) infection.Low dose (15μg H56 protein in 500nmol IC31) or high dose (50μg H56, 500nmol IC31) vaccine was administered intramuscularly thrice, at 56-day intervals. Antigen-specific T cell responses were measured by intracellular cytokine staining and antibody responses by ELISA.One hundred and twenty-six subjects were screened and 25 enrolled and vaccinated. No serious adverse events were reported. Nine subjects (36%) presented with transient cardiovascular adverse events. The H56:IC31 vaccine induced antigen-specific IgG responses and Th1 cytokine-expressing CD4+ T cells. M.tb-infected vaccinees had higher frequencies of H56-induced CD4+ T cells than uninfected vaccinees. Low dose vaccination induced more polyfunctional (IFN-γ+TNF-α+IL-2+) and higher frequencies of H56-specific CD4+ T cells compared with high dose vaccination. A striking increase in IFN-γ-only-expressing CD4+ T cells, displaying a CD45RA−CCR7− effector memory phenotype, emerged after the second high-dose vaccination in M.tb-infected vaccinees. TNF-α+IL-2+ H56-specific memory CD4+ T cells were detected mostly after low-dose H56 vaccination in M.tb-infected vaccinees, and predominantly expressed a CD45RA−CCR7+ central memory phenotype. Our results support further clinical testing of H56:IC31.