Tuberculosis (TB) remains one of the deadliest infectious diseases worldwide, posing great social and economic burden to affected countries. Novel vaccine approaches are needed to increase protective immunity against the causative agent Mycobacterium tuberculosis (Mtb) and to reduce the development of active TB disease in latently infected individuals. Donor-unrestricted T cell responses represent such novel potential vaccine targets. HLA-E-restricted T cell responses have been shown to play an important role in protection against TB and other infections, and recent studies have demonstrated that these cells can be primed in vitro. However, the identification of novel pathogen-derived HLA-E binding peptides presented by infected target cells has been limited by the lack of accurate prediction algorithms for HLA-E binding. In this study, we developed an improved HLA-E binding peptide prediction algorithm and implemented it to identify (to our knowledge) novel Mtb-derived peptides with capacity to induce CD8⁺ T cell activation and that were recognized by specific HLA-E-restricted T cells in Mycobacterium-exposed humans. Altogether, we present a novel algorithm for the identification of pathogen- or self-derived HLA-E-presented peptides.