Increasing numbers of studies are reporting the modification of prokaryotic proteins with novel glycans. These proteins are often associated with virulence factors of medically important pathogens. Herein, we describe the steps required to characterize prokaryotic glycoproteins by mass spectrometry, using flagellin isolated from Clostridium botulinum strain Langeland as an example. Both "top-down" and "bottom-up" approaches will be described for characterizing the purified glycoprotein at the whole protein and peptide levels. The preliminary steps toward structural characterization of novel prokaryotic glycans by mass spectrometry and NMR are also described.