BACKGROUND: Fusobacterium animalis (Fa) was identified as the most enriched Fusobacterium species in colorectal cancer (CRC). Recently, a group of Fa core genes were found to be highly expressed intratumorally and to favor intracellular survival. We hypothesized that, because they promote bacterial fitness in the intracellular niche, these genes might be targets of positive selection, a process that often underlies adaptation to variable environments. RESULTS: We performed an evolutionary analysis to identify selective events that occurred over different time frames, namely during the divergence of the Fusobacterium species and in the more recent separation of the Fa lineage from F. paranimalis. Results indicated that the coding sequences of these genes have been targeted by intense purifying selection, possibly as the result of their often-essential functions. However, localized signatures of positive selection were also detectable. During the divergence of Fusobacterium species, the major target of positive selection was represented by elongation factor-Tu, a finding that may be related to its moonlighting functions in adhesion and biofilm development. Additional targets were RpoC and the septum-determining protein MinD. We suggest that variations in the latter contribute to the observed differences in cell length and width between F. watanabei and Fa. We also searched for and detected beneficial changes that occurred specifically in the Fa lineage, suggesting that such variants promote intracellular growth or adaptation to the tumor microenvironment. The strongest target of selection was DnaK, which was shown to promote malignant transformation in other bacterial systems. Analysis of the selected sites in DnaK indicated that most of them are located in the C-terminal unstructured region and that they determine the appearance of eukaryotic linear motifs (ELMs). Specifically, one ELM is a casein kinase 2 phosphorylation site, whereas two additional ELMs are involved in SUMOylation and USP7-mediated deubiquitination. USP is a central modulator of the p53-MDM2 pathway and we propose that SUMOylation facilitates the nuclear import of Fa DnaK where USP7 promotes its stability. CONCLUSION: We identified specific proteins and amino acid changes that are expected to underlie phenotypic diversity in Fusobacteria. These data are relevant to inform future analyses of Fa oncogenic potential.