Abstract Purpose: While evidence indicates that Fusobacterium nucleatum (F. nucleatum) may promote colorectal carcinogenesis through its suppressive effect on T-cell–mediated antitumor immunity, the specific T-cell subsets involved remain uncertain. Experimental Design: We measured F. nucleatum DNA within tumor tissue by quantitative PCR on 933 cases (including 128 F. nucleatum–positive cases) among 4,465 incident colorectal carcinoma cases in two prospective cohorts. Multiplex immunofluorescence combined with digital image analysis and machine learning algorithms for CD3, CD4, CD8, CD45RO (PTPRC isoform), and FOXP3 measured various T-cell subsets. We leveraged data on Bifidobacterium, microsatellite instability (MSI), tumor whole-exome sequencing, and M1/M2-type tumor-associated macrophages [TAM; by CD68, CD86, IRF5, MAF, and MRC1 (CD206) multimarker assay]. Using the 4,465 cancer cases and inverse probability weighting method to control for selection bias due to tissue availability, multivariable-adjusted logistic regression analysis assessed the association between F. nucleatum and T-cell subsets. Results: The amount of F. nucleatum was inversely associated with tumor stromal CD3+ lymphocytes [multivariable OR, 0.47; 95% confidence interval (CI), 0.28–0.79, for F. nucleatum–high vs. -negative category; Ptrend = 0.0004] and specifically stromal CD3+CD4+CD45RO+ cells (corresponding multivariable OR, 0.52; 95% CI, 0.32–0.85; Ptrend = 0.003). These relationships did not substantially differ by MSI status, neoantigen load, or exome-wide tumor mutational burden. F. nucleatum was not significantly associated with tumor intraepithelial T cells or with M1 or M2 TAMs. Conclusions: The amount of tissue F. nucleatum is associated with lower density of stromal memory helper T cells. Our findings provide evidence for the interactive pathogenic roles of microbiota and specific immune cells.