Polyoxin is a group of structurally-related peptidyl nucleoside antibiotics bearing C-5 modifications on the nucleoside skeleton. Although the structural diversity and bioactivity preference of polyoxin are, to some extent, affected by such modifications, the biosynthetic logic for their occurence remains obscure. Here we report the identification of PolB in polyoxin pathway as an unusual UMP C-5 methylase with thymidylate synthase activity which is responsible for the C-5 methylation of the nucleoside skeleton. To probe its molecular mechanism, we determined the crystal structures of PolB alone and in complexes with 5-Br UMP and 5-Br dUMP at 2.15 Å, 1.76 Å and 2.28 Å resolutions, respectively. Loop 1 (residues 117–131), Loop 2 (residues 192–201) and the substrate recognition peptide (residues 94–102) of PolB exhibit considerable conformational flexibility and adopt distinct structures upon binding to different substrate analogs. Consistent with the structural findings, a PolB homolog that harbors an identical function from Streptomyces viridochromogenes DSM 40736 was identified. The discovery of UMP C5-methylase opens the way to rational pathway engineering for polyoxin component optimization, and will also enrich the toolbox for natural nucleotide chemistry.