Glycosylation of surface structures diversifies cells chemically and physically. Nucleotide-activated sialic acids commonly serve as glycosyl donors, particularly pseudaminic acid (Pse) and its stereoisomer legionaminic acid (Leg), which decorate eubacterial and archaeal surface layers or protein appendages. FlmG, a recently identified protein sialyltransferase, O-glycosylates flagellins, the subunits of the flagellar filament. We show that flagellin glycosylation and motility in Caulobacter crescentus and Brevundimonas subvibrioides is conferred by functionally insulated Pse and Leg biosynthesis pathways, respectively, and by specialized FlmG orthologs. We established a genetic glyco-profiling platform for the classification of Pse or Leg biosynthesis pathways, discovered a signature determinant of eubacterial and archaeal Leg biosynthesis, and validated it by reconstitution experiments in a heterologous host. Finally, by rewiring FlmG glycosylation using chimeras, we defined two modular determinants that govern flagellin glycosyltransferase specificity: a glycosyltransferase domain that either donates Leg or Pse and a specialized flagellin-binding domain that identifies the acceptor.