Purpose of Review To summarize the relationship between colorectal cancer (CRC), immunity, and the gut microbiome, focusing on the population of Fusobacterium, particularly Fusobacterium nucleatum, which may mediate CRC initiation and progression by inhibiting host anti-tumor immunity. Recent Findings The onset and advancement of CRC involves genetic and epigenetic alterations and are modified by dietary and environmental factors. There is increasing evidence suggesting that gut bacteria, such as Fusobacterium nucleatum, may promote CRC development. The mechanisms through which Fusobacterium nucleatum from the oral cavity colonizes the gut mucosa and affect CRC development and progression remain unclear. Data from metagenomics analyses have shown an enrichment of Fusobacterium nucleatum in CRC tissues, which has been confirmed by quantitative PCR for the 16S ribosomal RNA gene DNA sequence of Fusobacterium nucleatum. Recent studies also suggest that Fusobacterium nucleatum may preferentially bind to cancerous cells, aided by Annexin A1, specifically expressed in proliferating CRC cells. This is consistent with a previous report that although Fusobacterium nucleatum is detected in both colorectal adenoma and adenocarcinoma tissues, the fadA gene levels are significantly higher in the latter than in the former. Other potential mechanisms include the ability of Fusobacterium to produce cancer-associated metabolites or genotoxic factors and possibly a direct interaction with the host immune system. Supporting a possible interaction with the host immune system are recent data indicating that overload of Fusobacterium nucleatum elicits high levels of Fusobacterium nucleatum-specific antibodies in CRC patients, suggesting that Fusobacterium nucleatum may escape host humoral immune responses by evolving inside host cells. Additionally, it has been found that the interaction of Fusobacterium nucleatum with immune response to CRC differs by tumor microsatellite (MS) status, suggesting that Fusobacterium nucleatum and MS status interact to influence anti-tumor immune functions.