Mounting evidence suggests human leucocyte antigen (HLA) class I-restricted CD8(+) T cells play a role in protective immunity against tuberculosis yet relatively few epitopes specific for the causative organism, Mycobacterium tuberculosis, are reported. Here a total genome-wide screen of M. tuberculosis was used to identify putative HLA-B*3501 T cell epitopes. Of 479 predicted epitopes, 13 with the highest score were synthesized and used to restimulate lymphocytes from naturally exposed HLA-B*3501 healthy individuals in cultured and ex vivo enzyme-linked immunospot (ELISPOT) assays for interferon (IFN)-gamma. All 13 peptides elicited a response that varied considerably between individuals. For three peptides CD8(+) T cell lines were expanded and four of the 13 were recognized permissively through the HLA-B7 supertype family. Although further testing is required we show the genome-wide screen to be feasible for the identification of unknown mycobacterial antigens involved in immunity against natural infection. While the mechanisms of protective immunity against M. tuberculosis infection remain unclear, conventional class I-restricted CD8(+) T cell responses appear to be widespread throughout the genome.