Biofilm-forming benthic diatoms are key primary producers in coastal habitats, where they frequently dominate sunlit intertidal substrata. The development of gliding motility in raphid diatoms was a key molecular adaptation that contributed to their evolutionary success. However, the structure-function correlation between diatom adhesives utilized for gliding and their relationship to the extracellular matrix that constitutes the diatom biofilm is unknown. Here, we have used proteomics, immunolocalization, comparative genomics, phylogenetics and structural homology analysis to investigate the evolutionary history and function of diatom adhesive proteins. Our study identified eight proteins from the adhesive trails of Craspedostauros australis, of which four form a new protein family called Trailins that contain an enigmatic Choice-of-Anchor A (CAA) domain, which was acquired through horizontal gene transfer from bacteria. Notably, the CAA-domain shares a striking structural similarity with one of the most widespread domains found in ice-binding proteins (IPR021884). Our work offers new insights into the molecular basis for diatom biofilm formation, shedding light on the function and evolution of diatom adhesive proteins. This discovery suggests that there is a transition in the composition of biomolecules required for initial surface colonization and those utilized for 3D biofilm matrix formation.