Fusobacteria have been associated to different diseases, including colorectal cancer (CRC), but knowledge of which taxonomic groups contribute to specific conditions is incomplete. We analyzed the genetic diversity and relationships within the Fusobacterium genus. We report recent and ancestral recombination in core genes, indicating that fusobacteria have mosaic genomes and emphasizing that taxonomic demarcation should not rely on single genes/gene regions. Across databases, we found ample evidence of species miss-classification and of undescribed species, which are both expected to complicate disease association. By focusing on a lineage that includes F. periodonticum/pseudoperiodonticum and F. nucleatum, we show that genomes belong to four modern populations, but most known species/subspecies emerged from individual ancestral populations. Of these, the F. periodonticum/pseudoperiodonticum population experienced the lowest drift and displays the highest genetic diversity, in line with the less specialized distribution of these bacteria in oral sites. A highly drifted ancestral population instead contributed genetic ancestry to a new species, which includes genomes classified within the F. nucleatum animalis diversity in a recent CRC study. Thus, evidence herein calls for a re-analysis of F. nucleatum animalis features associated to CRC. More generally, our data inform future molecular profiling approaches to investigate the epidemiology of Fusobacterium-associated diseases.