Flagellins from Clostridium botulinum were shown to be post-translationally modified with novel glycan moieties by top-down MS analysis of purified flagellin protein from strains of various toxin serotypes. Detailed analyses of flagellin from two strains of C. botulinum demonstrated that the protein is modified by a novel glycan moiety of mass 417 Da in O-linkage. Bioinformatic analysis of available C. botulinum genomes identified a flagellar glycosylation island containing homologs of genes recently identified in Campylobacter coli that have been shown to be responsible for the biosynthesis of legionaminic acid derivatives. Structural characterization of the carbohydrate moiety was completed utilizing both MS and NMR spectroscopy, and it was shown to be a novel legionaminic acid derivative, 7-acetamido-5-(N-methyl-glutam-4-yl)-amino-3,5,7,9-tetradeoxy-D-glycero-alpha-D-galacto-nonulosonic acid, (alphaLeg5GluNMe7Ac). Electron transfer dissociation MS with and without collision-activated dissociation was utilized to map seven sites of O-linked glycosylation, eliminating the need for chemical derivatization of tryptic peptides prior to analysis. Marker ions for novel glycans, as well as a unique C-terminal flagellin peptide marker ion, were identified in a top-down analysis of the intact protein. These ions have the potential for use in for rapid detection and discrimination of C. botulinum cells, indicating botulinum neurotoxin contamination. This is the first report of glycosylation of Gram-positive flagellar proteins by the 'sialic acid-like' nonulosonate sugar, legionaminic acid.