Fusobacterium nucleatum is a gram-negative anaerobe that is prevalent in periodontal disease and infections of different parts of the body. The organism has remarkable adherence properties, binding to partners ranging from eukaryotic and prokaryotic cells to extracellular macromolecules. Understanding its adherence is important for understanding the pathogenesis of F. nucleatum. In this study, a novel adhesin, FadA (Fusobacterium adhesin A), was demonstrated to bind to the surface proteins of the oral mucosal KB cells. FadA is composed of 129 amino acid (aa) residues, including an 18-aa signal peptide, with calculated molecular masses of 13.6 kDa for the intact form and 12.6 kDa for the secreted form. It is highly conserved among F. nucleatum, Fusobacterium periodonticum, and Fusobacterium simiae, the three most closely related oral species, but is absent in the nonoral species, including Fusobacterium gonidiaformans, Fusobacterium mortiferum, Fusobacterium naviforme, Fusobacterium russii, and Fusobacterium ulcerans. In addition to FadA, F. nucleatum ATCC 25586 and ATCC 49256 also encode two paralogues, FN1529 and FNV2159, each sharing 31% identity with FadA. A double-crossover fadA deletion mutant, F. nucleatum 12230-US1, was constructed by utilizing a novel sonoporation procedure. The mutant had a slightly slower growth rate, yet its binding to KB and Chinese hamster ovarian cells was reduced by 70 to 80% compared to that of the wild type, indicating that FadA plays an important role in fusobacterial colonization in the host. Furthermore, due to its uniqueness to oral Fusobacterium species, fadA may be used as a marker to detect orally related fusobacteria. F. nucleatum isolated from other parts of the body may originate from the oral cavity.