Tuberculosis (TB) is an escalating global health problem and improved vaccines against TB are urgently needed. HLA-E restricted responses may be of interest for vaccine development since HLA-E displays very limited polymorphism (only 2 coding variants exist), and is not down-regulated by HIV-infection. The peptides from Mycobacterium tuberculosis (Mtb) potentially presented by HLA-E molecules, however, are unknown. Here we describe human T-cell responses to Mtb-derived peptides containing predicted HLA-E binding motifs and binding-affinity for HLA-E. We observed CD8(+) T-cell proliferation to the majority of the 69 peptides tested in Mtb responsive adults as well as in BCG-vaccinated infants. CD8(+) T-cells were cytotoxic against target-cells transfected with HLA-E only in the presence of specific peptide. These T cells were also able to lyse M. bovis BCG infected, but not control monocytes, suggesting recognition of antigens during mycobacterial infection. In addition, peptide induced CD8(+) T-cells also displayed regulatory activity, since they inhibited T-cell proliferation. This regulatory activity was cell contact-dependent, and at least partly dependent on membrane-bound TGF-beta. Our results significantly increase our understanding of the human immune response to Mtb by identification of CD8(+) T-cell responses to novel HLA-E binding peptides of Mtb, which have cytotoxic as well as immunoregulatory activity.