The functional role of CD8+ lymphocytes in tuberculosis remains poorly understood. Here, we depleted innate and/or adaptive CD8+ lymphocytes in macaques and show that loss of all CD8a expressing cells significantly impaired early control of Mycobacterium tuberculosis (Mtb) infection, leading to increased granuloma numbers, lung inflammation, and total bacterial burden. Analysis of barcoded Mtb from infected animals demonstrated that depletion of all CD8+ lymphocytes allowed increased initial establishment of Mtb in lungs and dissemination within lungs and to lymph nodes while depletion of only adaptive CD8+ T cells worsened bacterial control in lymph nodes. Flow cytometry and single-cell RNA-sequencing revealed polyfunctional cytotoxic CD8+ lymphocytes in control granulomas, while CD8-depleted animals were unexpectedly enriched in CD4 and gd T cells adopting incomplete cytotoxic signatures. Ligand-receptor analyses identified immune interactions associated with cytotoxic T cells, including IL-15 signaling in granulomas. These data support that CD8+ lymphocytes are required for early protection against Mtb and suggest polyfunctional cytotoxic responses as an attractive vaccine target.