The mucus layer covering the gastrointestinal tract is the first point of contact of the intestinal microbiota with the host. Cell surface macromolecules are critical for adherence of commensal bacteria to mucus but structural information is scarce. Here we report the first molecular and structural characterization of a novel cell-surface protein, Lar_0958 from Lactobacillus reuteri JCM 1112(T) , mediating adhesion of L. reuteri human strains to mucus. Lar_0958 is a modular protein of 133 kDa containing six repeat domains, an N-terminal signal sequence and a C-terminal anchoring motif (LPXTG). Lar_0958 homologues are expressed on the cell-surface of L. reuteri human strains, as shown by flow-cytometry and immunogold microscopy. Adhesion of human L. reuteri strains to mucus in vitro was significantly reduced in the presence of an anti-Lar_0958 antibody and Lar_0958 contribution to adhesion was further confirmed using a L. reuteri ATCC PTA 6475 lar_0958 KO mutant (6475-KO). The X-ray crystal structure of a single Lar_0958 repeat, determined at 1.5 Å resolution, revealed a divergent immunoglobulin (Ig)-like β-sandwich fold, sharing structural homology with the Ig-like inter-repeat domain of internalins of the food borne pathogen Listeria monocytogenes. These findings provide unique structural insights into cell-surface protein repeats involved in adhesion of Gram-positive bacteria to the intestine.