Background: Novel tuberculosis vaccines should be safe, immunogenic, and effective in various population groups, including HIV-infected individuals. In this phase II multi-centre, double-blind, placebo-controlled trial, the safety and immunogenicity of the novel H1/IC31 vaccine, a fusion protein of Ag85B-ESAT-6 (H1) formulated with the adjuvant IC31, was evaluated in HIV-infected adults. Methods: HIV-infected adults with CD4+ T cell counts >350/mm3 and without evidence of active tuberculosis were enrolled and followed until day 182. H1/IC31 vaccine or placebo was randomly allocated in a 5:1 ratio. The vaccine was administered intramuscularly at day 0 and 56. Safety assessment was based on medical history, clinical examinations, and blood and urine testing. Immunogenicity was determined by a short-term whole blood intracellular cytokine staining assay. Results: 47 of the 48 randomised participants completed both vaccinations. In total, 459 mild or moderate and 2 severe adverse events were reported. There were three serious adverse events in two vaccinees classified as not related to the investigational product. Local injection site reactions were more common in H1/IC31 versus placebo recipients (65.0% vs. 12.5%, p = 0.015). Solicited systemic and unsolicited adverse events were similar by study arm. The baseline CD4+ T cell count and HIV viral load were similar by study arm and remained constant over time. The H1/IC31 vaccine induced a persistent Th1-immune response with predominately TNF-α and IL-2 co-expressing CD4+ T cells, as well as polyfunctional IFN-γ, TNF-α and IL-2 expressing CD4+ T cells. Conclusion: H1/IC31 was well tolerated and safe in HIV-infected adults with a CD4+ Lymphocyte count greater than 350 cells/mm3. The vaccine did not have an effect on CD4+ T cell count or HIV-1 viral load. H1/IC31 induced a specific and durable Th1 immune response.