The gastrointestinal mucosal surface is the primary interface between internal host tissues and the vast microbiota. Mucins, key components of mucus, are high-molecular-weight glycoproteins characterized by the presence of many O-linked oligosaccharides to the core polypeptide. They play many biological functions, helping to maintain cellular homeostasis and to establish symbiotic relationships with complex microbiota. Mucin O-glycans exhibit a huge variety of peripheral sequences implicated in the binding of bacteria to the mucosal tissues, thereby playing a key role in the selection of specific species and in the tissue tropism displayed by commensal and pathogenic bacteria. Bacteria have evolved numerous strategies to colonize host mucosae, and among these are modulation of expression of cell surface adhesins which allow bacteria to bind to mucins. However, despite well structurally characterized adhesins and lectins, information on the nature and structure of oligosaccharides recognized by bacteria is still disparate. This review summarizes the current knowledge on the structure of epithelial mucin O-glycans and the interaction between host and commensal or pathogenic bacteria mediated by mucins.