The bacterium Pseudoalteromonas tunicata is a common surface colonizer of marine eukaryotes, including the macroalga Ulva australis.Genomic analysis of P. tunicata identified genes potentially involved in surface colonization, including genes with homology to bacterial virulence factors that mediate attachment. Of particular interest is the presence of a gene, designated ptlL32, encoding an ortholog to the Leptospira lipoprotein LipL32, which has been shown to facilitate the interaction of Leptospira sp. with host extracellular matrix (ECM) structures and is thought to be an important virulence trait for pathogenic Leptospira. To investigate the role of PtlL32 in the colonization by P. tunicata we constructed and characterized a DeltaptlL32 mutant strain. Whilst P. tunicata DeltaptlL32 bound to an abiotic surface with the same capacity as the wild type strain, it had a marked effect on the ability of P. tunicata to bind to ECM, suggesting a specific role in attachment to biological surfaces. Loss of PtlL32 also significantly reduced the capacity for P. tunciata to colonize the host algal surface demonstrating a clear role for this protein as a host-colonization factor. PtlL32 appears to have a patchy distribution across specific groups of environmental bacteria and phylogenetic analysis of PtlL32 orthologous proteins from non-Leptospira species suggests it may have been acquired via horizontal gene transfer between distantly related lineages. This study provides the first evidence for an attachment function for a LipL32-like protein outside the Leptospira and thereby contributes to the understanding of host colonization in ecologically distinct bacterial species.