Though widely used, the BCG vaccine has had little apparent effect on rates of adult pulmonary tuberculosis. Moreover, the risk of disseminated BCG disease in immunocompromised individuals means that improved TB vaccines ideally need to be able to efficiently prime mycobacterially-naïve individuals as well as boost individuals previously vaccinated with BCG. Protective immunity against Mycobacterium tuberculosis is thought to depend on the generation of a Th1-type cellular immune response characterized by interferon-gamma (IFN-gamma) production. In the present study, we monitored safety and IFN-gamma responses in healthy TB-naïve humans receiving an entirely novel vaccine, composed of the fusion protein Ag85B-ESAT-6, administered at 0 and 2 months either as recombinant protein alone or combined with two concentrations of the novel adjuvant IC31. Vaccination did not cause local or systemic adverse effects besides transient soreness at the injection site, but it elicited strong antigen-specific T cell responses against H1 and both the Ag85B and the ESAT-6 components. These strong responses persisted through 2.5 years of follow-up, indicating the induction of a substantial memory response in the vaccine recipients.