Growing evidence indicates a role for the gut microbiota in modulating anti-tumor treatment efficacy in human cancer. Here we study mucosa-associated invariant T (MAIT) cells to look for evidence of bacterial antigen recognition in human colon, lung, and kidney carcinomas. Using mass cytometry and single-cell mRNA sequencing, we identify a tumor-infiltrating MAIT cell subset expressing CD4 and Foxp3 and observe high expression of CD39 on MAIT cells from colorectal cancer (CRC) only, which we show in vitro to be expressed specifically after TCR stimulation. We further reveal that these cells are phenotypically and functionally exhausted. Sequencing data show high bacterial infiltration in CRC tumors and highlight an enriched species, Fusobacteria nucleatum, with capability to activate MAIT cells in a TCR-dependent way. Our results provide evidence of a MAIT cell response to microbial antigens in CRC and could pave the way for manipulating MAIT cells or the microbiome for cancer therapy.