ABSTRACT The diverse Fusobacterium genus contains species implicated in multiple clinical pathologies, including periodontal disease, preterm birth, and colorectal cancer. The lack of genetic tools for manipulating these organisms leaves us with little understanding of the genes responsible for adherence to and invasion of host cells. Actively invading Fusobacterium species can enter host cells independently, whereas passively invading species need additional factors, such as compromise of mucosal integrity or coinfection with other microbes. We applied whole-genome sequencing and comparative analysis to study the evolution of active and passive invasion strategies and to infer factors associated with active forms of host cell invasion. The evolution of active invasion appears to have followed an adaptive radiation in which two of the three fusobacterial lineages acquired new genes and underwent expansions of ancestral genes that enable active forms of host cell invasion. Compared to passive invaders, active invaders have much larger genomes, encode FadA-related adhesins, and possess twice as many genes encoding membrane-related proteins, including a large expansion of surface-associated proteins containing the MORN2 domain of unknown function. We predict a role for proteins containing MORN2 domains in adhesion and active invasion. In the largest and most comprehensive comparison of sequenced Fusobacterium species to date, we have generated a testable model for the molecular pathogenesis of Fusobacterium infection and illuminate new therapeutic or diagnostic strategies. IMPORTANCE Fusobacterium species have recently been implicated in a broad spectrum of human pathologies, including Crohn’s disease, ulcerative colitis, preterm birth, and colorectal cancer. Largely due to the genetic intractability of member species, the mechanisms by which Fusobacterium causes these pathologies are not well understood, although adherence to and active invasion of host cells appear important. We examined whole-genome sequence data from a diverse set of Fusobacterium species to identify genetic determinants of active forms of host cell invasion. Our analyses revealed that actively invading Fusobacterium species have larger genomes than passively invading species and possess a specific complement of genes—including a class of genes of unknown function that we predict evolved to enable host cell adherence and invasion. This study provides an important framework for future studies on the role of Fusobacterium in pathologies such as colorectal cancer.