Tuberculosis (TB) remains a global health problem, with vaccination being a necessary strategy for disease containment and elimination. A TB vaccine should be safe and immunogenic as well as efficacious in all affected populations, including HIV-infected individuals. We investigated the induction and maintenance of vaccine-induced memory CD4(+) T cells following vaccination with the subunit vaccine H1/IC31. H1/IC31 was inoculated twice on study days 0 and 56 among HIV-infected adults with CD4(+) lymphocyte counts of >350 cells/mm(3). Whole venous blood stimulation was conducted with the H1 protein, and memory CD4(+) T cells were analyzed using intracellular cytokine staining and polychromatic flow cytometry. We identified high responders, intermediate responders, and nonresponders based on detection of interleukin-2 (IL-2), tumor necrosis factor alpha (TNF-α), and gamma interferon (IFN-γ) expressing central (TCM) and effector memory CD4(+) T cells (TEM) 182 days after the first immunization. Amplicon-based transcript quantification using next-generation sequencing was performed to identify differentially expressed genes that correlated with vaccine-induced immune responses. Genes implicated in resolution of inflammation discriminated the responders from the nonresponders 3 days after the first inoculation. The volunteers with higher expression levels of genes involved in antiviral innate immunity at baseline showed impaired H1-specific TCM and TEM maintenance 6 months after vaccination. Our study showed that in HIV-infected volunteers, expression levels of genes involved in the antiviral innate immune response affected long-term maintenance of H1/IC31 vaccine-induced cellular immunity. (The clinical trial was registered in the Pan African Clinical Trials Registry [PACTR] with the identifier PACTR201105000289276.).