Glycosylation of proteins is known to impart novel physical properties and biological roles to proteins from both eukaryotes and prokaryotes. In this study, gel-based glycoproteomics were used to identify glycoproteins of the potential biothreat agent Burkholderia pseudomallei and the closely related but nonpathogenic B. thailandensis. Top-down and bottom-up mass spectrometry (MS) analyses identified that the flagellin proteins of both species were posttranslationally modified by novel glycans. Analysis of proteins from two strains of each species demonstrated that B. pseudomallei flagellin proteins were modified with a glycan with a mass of 291 Da, while B. thailandensis flagellin protein was modified with related glycans with a mass of 300 or 342 Da. Structural characterization of the B. thailandensis carbohydrate moiety suggests that it is an acetylated hexuronic acid. In addition, we have identified through mutagenesis a gene from the lipopolysaccharide (LPS) O-antigen biosynthetic cluster which is involved in flagellar glycosylation, and inactivation of this gene eliminates flagellar glycosylation and motility in B. pseudomallei. This is the first report to conclusively demonstrate the presence of a carbohydrate covalently linked to a protein in B. pseudomallei and B. thailandensis, and it suggests new avenues to explore in order to examine the marked differences in virulence between these two species.