Dental biofilm development is a sequential process, and adherence between microbes and the salivary pellicle (adhesion) as well as among different microbes (co-adhesion or coaggregation) plays a critical role in building a biofilm community. The Veillonella species are among the most predominant species in the oral cavity and coaggregate with many initial, early, middle, and late colonizers. Similar to oral fusobacteria, they are also considered bridging species in biofilm development. However, the mechanism of this ability has yet to be reported, due to the previous lack of a genetic transformation system in the entire genus. In this study, we used our recently discovered transformable Veillonella strain, Veillonella atypica OK5, to probe the mechanism of coaggregation between Veillonella species and other oral bacteria. By insertional inactivation of all eight putative hemagglutinin genes, we identified one gene, hag1, which is involved in V. atypica coaggregation with the initial colonizers Streptococcus gordonii, Streptococcus oralis and Streptococcus cristatus, and the periodontal pathogen Porphyromonas gingivalis. The hag1 mutant also abolished adherence to human buccal cells. Inhibition assays using various chemical or physiological treatments suggest different mechanisms being involved in coaggregation with different partners. The entire hag1 gene was sequenced and shown to be the largest known bacterial hemagglutinin gene.