In recent years, the investigation of bacterial protein glycosylation has progressed rapidly and what was once believed to be an oddity of few bacterial strains now seems to be a more general pattern of post-translational modifications. Despite their clinical importance, bacterial glycoproteins remain under-explored compared to their eukaryotic counterparts, mainly due to a lack of suitable analytical tools. Here we present a newly developed glycoproteomics technique, termed BEMAP, which allows for efficient and selective enrichment of O-linked glycopeptides from a complex protein extract for subsequent mass-spectrometric identification. Using BEMAP we have identified close to one hundred glycoproteins from the outer membrane of enterotoxigenic Escherichia coli (ETEC), including several known virulence factors. Genetic analysis further reveals that protein glycosylation is important for bacterial motility as well as adhesion to polarized human intestinal epithelial cells. Finally, we have discovered a surprising link between protein glycosylation and regulation of gene expression in bacteria by demonstrating that levels of glycoprotein-encoding mRNA transcripts are reduced more than 1.000-fold in the absence of the corresponding glycosyltransferases. It appears that glycosyltransferases not only perform post-translational modification of a specific protein subset but also affects, directly or indirectly, the synthesis of these proteins. RNA-seq analyses reveal that hundreds of genes are affected by deletion of glycosyltransferases, indicating that modulation of transcription factor activity through glycosylation may take place in bacteria as it does in eukaryotes.