Many bacteria glycosylate flagellin on serine or threonine residues using pseudaminic acid (Pse) or other sialic acid-like donor sugars. Successful reconstitution of Pse-dependent sialylation by the conserved Maf-type flagellin glycosyltransferase (fGT) may require (a) missing component(s). Here, we characterize both Maf paralogs in the Gram-negative bacterium Shewanella oneidensis MR-1 and reconstitute Pse-dependent glycosylation in heterologous hosts. Remarkably, we uncovered distinct acceptor determinants and target specificities for each Maf. Whereas Maf-1 uses its C-terminal tetratricopeptide repeat (TPR) domain to confer flagellin acceptor and O-glycosylation specificity, Maf-2 requires the newly identified conserved specificity factor, glycosylation factor for Maf (GlfM), to form a ternary complex with flagellin. GlfM orthologs are co-encoded with Maf-2 in Gram-negative and Gram-positive bacteria and require an invariant aspartate in their four-helix bundle to function with Maf-2. Thus, convergent fGT evolution underlies distinct flagellin-binding modes in tripartite versus bipartite systems and, consequently, distinct O-glycosylation preferences of acceptor serine residues with Pse.