Modification of the phosphate groups of lipid A with 4-amino-4-deoxy-L-arabinose (L-Ara4N) is required for resistance to polymyxin and cationic antimicrobial peptides in Escherichia coli and Salmonella typhimurium. We previously demonstrated that the enzyme ArnA catalyzes the NAD+-dependent oxidative decarboxylation of UDP-glucuronic acid to yield the UDP-4''-ketopentose, uridine 5'-diphospho-beta-(L-threo-pentapyranosyl-4''-ulose), which is converted by ArnB to UDP-beta-(L-Ara4N). E. coli ArnA is a bi-functional enzyme with a molecular mass of approximately 74 kDa. The oxidative decarboxylation of UDP-glucuronic acid is catalyzed by the 345-residue C-terminal domain of ArnA. The latter shows sequence similarity to enzymes that oxidize the C-4'' position of sugar nucleotides, like UDP-galactose epimerase, dTDP-glucose-4,6-dehydratase, and UDP-xylose synthase. We now show that the 304-residue N-terminal domain catalyzes the N-10-formyltetrahydrofolate-dependent formylation of the 4''-amine of UDP-L-Ara4N, generating the novel sugar nucleotide, uridine 5'-diphospho-beta-(4-deoxy-4-formamido-L-arabinose). The N-terminal domain is highly homologous to methionyl-tRNA(f)Met formyltransferase. The structure of the formylated sugar nucleotide generated in vitro by ArnA was validated by 1H and 13C NMR spectroscopy. The two domains of ArnA were expressed independently as active proteins in E. coli. Both were required for maintenance of polymyxin resistance and L-Ara4N modification of lipid A. We conclude that N-formylation of UDP-L-Ara4N is an obligatory step in the biosynthesis of L-Ara4N-modified lipid A in polymyxin-resistant mutants. We further demonstrate that only the formylated sugar nucleotide is converted in vitro to an undecaprenyl phosphate-linked form by the enzyme ArnC. Because the L-Ara4N unit attached to lipid A is not derivatized with a formyl group, we postulate the existence of a deformylase, acting later in the pathway.