The unsheathed flagellar filament of Shewanella oneidensis MR-1 is composed of two highly homologous flagellins, FlaA, and the major structural unit, FlaB. We identified a gene cluster, SO_3261-SO_3265 (now sfmABCDE), that is required for the formation of a fully functional filament and for motility. The predicted function of the corresponding gene products strongly indicated a role in flagellin modification. Accordingly, loss of sfmABCDE results in a significant mass shift of both FlaA and FlaB. Mass spectroscopy analysis and single residue substitutions identified five serine residues in both flagellins that are modified via O-linkage. Modeling of the flagellin structures strongly suggests that at least four of the modified residues are exposed to the filament's surface. However, none of the five serine residues solely is crucial for function and assembly. Structural analysis of the flagellin modification revealed that it likely contains a nonulosonic acid (274 Da) linked to each glycosylated serine. The putative nonulosonic acid is further substituted with a 236 Da moiety which can carry additional methyl groups (250 Da, 264 Da). In addition, at least 5 lysine residues in FlaB and one in FlaA were found to be methylated. Based on homology comparisons we suggest that smfABCDE is required for species-specific flagellin modification in S. oneidensis MR-1.