To unravel the biological function of the widely used probiotic bacterium Lactobacillus rhamnosus GG, we compared its 3.0-Mbp genome sequence with the similarly sized genome of L. rhamnosus LC705, an adjunct starter culture exhibiting reduced binding to mucus. Both genomes demonstrated high sequence identity and synteny. However, for both strains, genomic islands, 5 in GG and 4 in LC705, punctuated the colinearity. A significant number of strain-specific genes were predicted in these islands (80 in GG and 72 in LC705). The GG-specific islands included genes coding for bacteriophage components, sugar metabolism and transport, and exopolysaccharide biosynthesis. One island only found in L. rhamnosus GG contained genes for 3 secreted LPXTG-like pilins (spaCBA) and a pilin-dedicated sortase. Using anti-SpaC antibodies, the physical presence of cell wall-bound pili was confirmed by immunoblotting. Immunogold electron microscopy showed that the SpaC pilin is located at the pilus tip but also sporadically throughout the structure. Moreover, the adherence of strain GG to human intestinal mucus was blocked by SpaC antiserum and abolished in a mutant carrying an inactivated spaC gene. Similarly, binding to mucus was demonstrated for the purified SpaC protein. We conclude that the presence of SpaC is essential for the mucus interaction of L. rhamnosus GG and likely explains its ability to persist in the human intestinal tract longer than LC705 during an intervention trial. The presence of mucus-binding pili on the surface of a nonpathogenic Gram-positive bacterial strain reveals a previously undescribed mechanism for the interaction of selected probiotic lactobacilli with host tissues.