MHC Ib-restricted CD8+ T cells have been implicated in host defense against Mycobacterium tuberculosis (Mtb) infection. However, the relative contribution of various MHC Ib-restricted T cell populations to anti-mycobacterial immunity remains elusive. In this study, we used mice that lack MHC Ia (Kb-/-Db-/-), MHC Ia/H2-M3 (Kb-/-Db-/-M3-/-), or β2m (β2m-/-) to study the role of M3-restricted and other MHC Ib-restricted T cells in immunity against Mtb. Unlike their dominant role in Listeria infection, we found that M3-restricted CD8+ T cells only represented a small proportion of the CD8+ T cells responding to Mtb infection. Non-M3, MHC Ib-restricted CD8+ T cells expanded preferentially in the lungs of Mtb-infected Kb-/-Db-/-M3-/- mice, exhibited polyfunctional capacities and conferred protection against Mtb. These MHC Ib-restricted CD8+ T cells recognized several Mtb-derived protein antigens at a higher frequency than MHC Ia-restricted CD8+ T cells. The presentation of Mtb antigens to MHC Ib-restricted CD8+ T cells was mostly β2m-dependent but TAP-independent. Interestingly, a large proportion of Mtb-specific MHC Ib-restricted CD8+ T cells in Kb-/-Db-/-M3-/- mice were Qa-2-restricted while no considerable numbers of MR1 or CD1-restricted Mtb-specific CD8+ T cells were detected. Our findings indicate that nonclassical CD8+ T cells other than the known M3, CD1, and MR1-restricted CD8+ T cells contribute to host immune responses against Mtb infection. Targeting these MHC Ib-restricted CD8+ T cells would facilitate the design of better Mtb vaccines with broader coverage across MHC haplotypes due to the limited polymorphism of MHC class Ib molecules.