Identification of CD8(+) T cell antigens/epitopes expressed by human pathogens with large genomes is especially challenging, yet necessary for vaccine development. Immunity to tuberculosis, a leading cause of mortality worldwide, requires CD8(+) T cell immunity, yet the repertoire of CD8 antigens/epitopes remains undefined. We used integrated computational and proteomic approaches to screen 10% of the Mycobacterium tuberculosis (Mtb) proteome for CD8 Mtb antigens. We designed a weighting schema based upon a Multiple Attribute Decision Making:framework to select 10% of the Mtb proteome with a high probability of containing CD8(+) T cell epitopes. We created a synthetic peptide library consisting of 15-mers overlapping by 11 aa. Using the interferon-γ ELISPOT assay and Mtb-infected dendritic cells as antigen presenting cells, we screened Mtb-specific CD8(+) T cell clones restricted by classical MHC class I molecules (MHC class Ia molecules), that were isolated from Mtb-infected humans, against this library. Three novel CD8 antigens were unambiguously identified: the EsxJ family (Rv1038c, Rv1197, Rv3620c, Rv2347c, Rv1792), PE9 (Rv1088), and PE_PGRS42 (Rv2487c). The epitopes are B5701-restricted EsxJ24-34, B3905-restricted PE953-67, and B3514-restricted PE_PGRS4248-56, respectively. The utility of peptide libraries in identifying unknown epitopes recognized by classically restricted CD8(+) T cells was confirmed, which can be applied to other intracellular pathogens with large size genomes. In addition, we identified three novel Mtb epitopes/antigens that may be evaluated for inclusion in vaccines and/or diagnostics for tuberculosis.