To successfully colonize the oral cavity, bacteria must directly or indirectly adhere to available oral surfaces. Fusobacterium nucleatum plays an important role in oral biofilm community development due to its broad adherence abilities, serving as a bridge between members of the oral biofilm that cannot directly bind to each other. In our efforts to characterize the molecular mechanisms utilized by F. nucleatum to physically bind to key members of the oral community, we investigated the involvement of F. nucleatum outer membrane proteins in its ability to bind to the pioneer biofilm colonizer, Streptococcus gordonii. Here, we present evidence that in addition to the previously characterized fusobacterial adhesin RadD, the interaction between F. nucleatum ATCC 23726 and S. gordonii V288 involves a second outer membrane protein, which we named coaggregation mediating protein A (CmpA). We also characterized the role of CmpA in dual‐species biofilm formation with S. gordonii V288, evaluated growth‐phase‐dependent as well as biofilm expression profiles of radD and cmpA, and confirmed an important role for CmpA, especially under biofilm growth conditions. Our findings underscore the complex set of specific interactions involved in physical binding and thus community integration of interacting bacterial species. This complex set of interactions could have critical implications for the formation and maturation of the oral biofilms in vivo, and could provide clues to the mechanism behind the distribution of organisms inside the human oral cavity.