Although CD8(+) T cells help control Mycobacterium tuberculosis infection, their M. tuberculosis Ag repertoire, in vivo frequency, and functionality in human tuberculosis (TB) remains largely undefined. We have performed genome-based bioinformatics searches to identify new M. tuberculosis epitopes presented by major HLA class I supertypes A2, A3, and B7 (covering 80% of the human population). A total of 432 M. tuberculosis peptides predicted to bind to HLA-A*0201, HLA-A*0301, and HLA-B*0702 (representing the above supertypes) were synthesized and HLA-binding affinities determined. Peptide-specific CD8(+) T cell proliferation assays (CFSE dilution) in 41 M. tuberculosis-responsive donors identified 70 new M. tuberculosis epitopes. Using HLA/peptide tetramers for the 18 most prominently recognized HLA-A*0201-binding M. tuberculosis peptides, recognition by cured TB patients' CD8(+) T cells was validated for all 18 epitopes. Intracellular cytokine staining for IFN-γ, IL-2, and TNF-α revealed mono-, dual-, as well as triple-positive CD8(+) T cells, indicating these M. tuberculosis peptide-specific CD8(+) T cells were (poly)functional. Moreover, these T cells were primed during natural infection, because they were absent from M. tuberculosis-noninfected individuals. Control CMV peptide/HLA-A*0201 tetramers stained CD8(+) T cells in M. tuberculosis-infected and noninfected individuals equally, whereas Ebola peptide/HLA-A*0201 tetramers were negative. In conclusion, the M. tuberculosis-epitope/Ag repertoire for human CD8(+) T cells is much broader than hitherto suspected, and the newly identified M. tuberculosis Ags are recognized by (poly)functional CD8(+) T cells during control of infection. These results impact on TB-vaccine design and biomarker identification.