Lactobacilli are normal constituents of the intestinal microbiota, and some strains show the capacity to bind to extracellular matrix proteins and components of the mucosal layer, which represents an adaptation to persist in this niche. A shotgun phage-display library of Lactobacillus casei BL23 was constructed and screened for peptides able to bind to fibronectin and collagen. Clones showing binding to these proteins were isolated, which encoded overlapping fragments of a putative transcriptional regulator (LCABL_29260), a hypothetical protein exclusively found in the L. casei/rhamnosus group (LCABL_01820), and a putative phage-related endolysin (LCABL_13470). The construction of different glutathione S-transferase (GST) fusions confirmed the binding activity and demonstrated that the three identified proteins could interact with fibronectin, fibrinogen, and collagen. The results illustrate the utility of phage display for the isolation of putative adhesins in lactobacilli. However, it remains to be determined whether the primary function of these proteins actually is adhesion to mucosal surfaces.