Fosfazinomycin A is a phosphonate natural product in which the C-terminal carboxylate of a Val–Arg dipeptide is connected to methyl 2-hydroxy-2-phosphono-acetate (Me-HPnA) via a unique hydrazide linkage. We report here that Me-HPnA is generated from phosphonoacetaldehyde (PnAA) in three biosynthetic steps through the combined action of an O-methyltransferase (FzmB) and an α-ketoglutarate (α-KG) dependent non-heme iron dioxygenase (FzmG). Unexpectedly, the latter enzyme is involved in two different steps, oxidation of the PnAA to phosphonoacetic acid as well as hydroxylation of methyl 2-phosphonoacetate. The N-methyltransferase (FzmH) was able to methylate Arg-NHNH2 (3) to give Arg-NHNHMe (4), constituting the second segment of the fosfazinomycin molecule. Methylation of other putative intermediates such as desmethyl fosfazinomycin B was not observed. Collectively, our current data support a convergent biosynthetic pathway to fosfazinomycin.