Bacterial adhesion is a fundamental process which enables colonisation of niche environments and is key for infection. However, in Legionella pneumophila, the causative agent of Legionnaires' disease, these processes are not well understood. The Legionella collagen-like protein (Lcl) is an extracellular peripheral membrane protein that recognises sulphated glycosaminoglycans on the surface of eukaryotic cells, but also stimulates bacterial aggregation in response to divalent cations. Here we report the crystal structure of the Lcl C-terminal domain (Lcl-CTD) and present a model for intact Lcl. Our data reveal that Lcl-CTD forms an unusual trimer arrangement with a positively charged external surface and negatively charged solvent exposed internal cavity. Through molecular dynamics simulations, we show how the glycosaminoglycan chondroitin-4-sulphate associates with the Lcl-CTD surface via distinct binding modes. Our findings show that Lcl homologs are present across both the Pseudomonadota and Fibrobacterota-Chlorobiota-Bacteroidota phyla and suggest that Lcl may represent a versatile carbohydrate-binding mechanism.