is a bacterium associated with colorectal cancer (CRC) tumorigenesis, progression, and metastasis. Fap2 is a fusobacteria-specific outer membrane galactose-binding lectin that mediates adherence to and invasion of CRC tumors. Advances in omics analyses provide an opportunity to profile and identify microbial genomic features that correlate with the cancer-associated bacterial virulence factor Fap2. Here, we analyze genomes of colon tumor isolates and find that a family of post-translational modification enzymes containing Fic domains is associated with Fap2 positivity in these strains. We demonstrate that Fic family genes expand with the presence of Fap2 in the fusobacterial pangenome. Through comparative genomic analysis, we find that Fap2 Fusobacteriota are highly enriched with Fic gene families compared to other cancer-associated and human gut microbiome bacterial taxa. Using a global data set of CRC shotgun metagenomes, we show that fusobacterial Fic and Fap2 genes frequently co-occur in the fecal microbiomes of individuals with late-stage CRC. We further characterize specific Fic gene families harbored by Fap2 genomes and detect recombination events and elements of horizontal gene transfer via synteny analysis of Fic gene loci. Exposure of a strain to a colon adenocarcinoma cell line increases gene expression of fusobacterial Fic and virulence-associated adhesins. Finally, we demonstrate that Fic proteins are synthesized by as Fic peptides are detectable in monoculture supernatants. Taken together, our study uncovers Fic genes as potential virulence factors in Fap2 fusobacterial genomes.IMPORTANCEAccumulating data support that bacterial members of the intra-tumoral microbiota critically influence colorectal cancer progression. Yet, relatively little is known about non-adhesin fusobacterial virulence factors that may influence carcinogenesis. Our genomic analysis and expression assays in fusobacteria identify Fic domain-containing genes, well-studied virulence factors in pathogenic bacteria, as potential fusobacterial virulence features. The Fic family proteins that we find are encoded by fusobacteria and expressed by merit future investigation to assess their roles in colorectal cancer development and progression.