The attachment of sugars to proteins via side-chain oxygen atoms (O-linked glycosylation) is seen in all three domains of life. However, a lack of widely-applicable analytical tools has restricted the study of this process, particularly in bacteria. In E. coli, only four O-linked glycoproteins have previously been characterized. Here we present a glycoproteomics technique, termed BEMAP, which is based on the beta-elimination of O-linked glycans followed by Michael-addition of a phosphonic acid derivative, and subsequent titanium dioxide enrichment. This strategy allows site-specific mass-spectrometric identification of proteins with O-linked glycan modifications in a complex biological sample. Using BEMAP we identified cell surface-associated and membrane vesicle glycoproteins from Enterotoxigenic E. coli (ETEC) and non-pathogenic E. coli K-12. We identified 618 glycosylated Serine and Threonine residues mapping to 140 proteins in ETEC, including several known virulence factors, and 34 in E. coli K-12. The two strains had 32 glycoproteins in common. Remarkably, the majority of the ETEC glycoproteins were conserved in both strains but nevertheless were only glycosylated in the pathogen. Therefore, bacterial O-linked glycosylation is much more extensive than previously thought, and is especially important to the pathogen.