Reactivation tuberculosis (TB) is a serious problem in immunocompromised individuals, especially those with human immunodeficiency virus (HIV) coinfection. The adaptive immune response mediated by CD4+ and CD8+ T cells is known to confer protection against TB. Hence, vaccines against TB are designed to activate these two components of the immune system. Anti-TB DNA vaccines encoding the immunodominant proteins Ag85A, Ag85B, and PstS-3 from Mycobacterium tuberculosis are ineffective in mice lacking CD4+ T cells (CD4-/- mice). In this study, we demonstrate that reconstitution of the T-cell compartment in CD4-/- mice restores vaccine-specific antibody and gamma interferon (IFN-gamma) responses to these DNA vaccines. The magnitude of the immune responses correlated with the extent of reconstitution of the CD4+-T-cell compartment. Reconstituted mice vaccinated with DNA encoding PstS-3, known to encode a dominant D(b)-restricted CD8+-T-cell epitope, displayed CD8+-T-cell responses not observed in CD4-/- mice. M. tuberculosis challenge in reconstituted mice led to the extravasation of IFN-gamma-producing CD4+ and CD8+ T cells into lungs, the primary site of bacterial replication. Importantly, a reconstitution of 12 to 15% of the CD4+-T-cell compartment resulted in Ag85B plasmid DNA-mediated protection against a challenge M. tuberculosis infection. Our findings provide evidence that anti-TB DNA vaccines could be effective in immunodeficient individuals after CD4+-T-lymphocyte reconstitution, as may occur following antiretroviral therapy in HIV+ patients.