Fusobacterium nucleatum is implicated in accelerating colorectal cancer (CRC) and is found within metastatic CRC cells in patient biopsies. Here, we found that bacterial invasion of CRC cells and cocultured immune cells induced a differential cytokine secretion that may contribute to CRC metastasis. We used a modified galactose kinase markerless gene deletion approach and found that F. nucleatum invaded cultured HCT116 CRC cells through the bacterial surface adhesin Fap2. In turn, Fap2-dependent invasion induced the secretion of the proinflammatory cytokines IL-8 and CXCL1, which are associated with CRC progression and promoted HCT116 cell migration. Conditioned medium from F. nucleatum–infected HCT116 cells caused naïve cells to migrate, which was blocked by depleting CXCL1 and IL-8 from the conditioned medium. Cytokine secretion from HCT116 cells and cellular migration were attenuated by inhibiting F. nucleatum host-cell binding and entry using galactose sugars, l-arginine, neutralizing membrane protein antibodies, or fap2 deletion. F. nucleatum also induces the mobilization of immune cells in the tumor microenvironment. However, in neutrophils and macrophages, the bacterial-induced secretion of cytokines was Fap2 independent. Thus, our findings show that F. nucleatum both directly and indirectly modulates immune and cancer cell signaling and migration. Because increased IL-8 and CXCL1 production in tumors is associated with increased metastatic potential and cell seeding, poor prognosis, and enhanced recruitment of tumor-associated macrophages and fibroblasts, we propose that inhibition of host-cell binding and invasion, potentially through vaccination or novel galactoside compounds, could be an effective strategy for reducing F. nucleatum–associated CRC metastasis.