The human microbiota modulates cancer progression through largely unexplored mechanisms. Defining causal pathways is essential for monitoring and fine-tuning the microbiota to improve cancer treatment. Given that amino acid (aa) metabolism is often dysregulated in cancer, we assessed the role of microbiota pathways that modulate intestinal aa levels on colorectal tumor progression in mice. We found that the Bacteroides gene bo-ansB affects tumor responses to dietary asparagine (Asn) by reducing intestinal Asn levels. In mice receiving dietary Asn, bo-ansB promotes tumor progression by altering tumor-infiltrating CD8+ T cells. Mechanistically, bo-ansB depletes Asn in the tumor microenvironment (TME), suppressing the expression of an Asn transporter (SLC1A5) in CD8+ T cells and impairing their stem-like properties and effector functions. In humans, microbiota-encoded genes contributing to aa depletion are associated with colorectal cancer progression. Collectively, these findings reveal nutrient-dependent modulation of anticancer immunity by the gut microbiota and identify diet-microbiota-cancer crosstalk as a potential therapeutic target.