MR1-restricted mucosal-associated invariant T (MAIT) cells recognize microbial metabolites and play an important role in immunity to infection, however, the role they play in tumor immunity is unclear. Here we show that MAIT cell-deficient mice are more resistant to subcutaneous and lung metastasis B16F10 tumor growth compared to control mice, an effect that was associated with enhanced NK cell numbers and was NK cell-dependent. Analysis of this interplay in cancer patients also revealed that a high expression of a novel MAIT gene signature negatively impacted the prognostic significance of NK cells. Paradoxically, pre-pulsing tumors with MAIT cell antigens, or antigen-mediated MAIT cell activation in vivo, enhanced immunity against B16F10 and E0771 lung tumor metastasis. Furthermore, MAIT cell activation effectively reduced metastatic burden in a more stringent model of established lung metastases in mice. These effects were associated with enhanced NK cell responses and increased expression of both IFNγ-dependent and inflammatory genes in NK cells, which was neutralized by IFNγ blockade. Importantly, activated human MAIT cells also enhanced the function of NK cells isolated from patient tumor samples. These findings provide insight into the contrasting roles that MAIT cells can play in controlling anti-tumor immune responses depending on their activation status, in both mice and humans, and suggest potential therapeutic avenues for exploiting their potential anti-tumor properties for cancer treatment.