The wobble uridine of certain bacterial and mitochondrial tRNAs is modified, at position 5, through an unknown reaction pathway that utilizes the evolutionarily conserved MnmE and GidA proteins. The resulting modification (a methyluridine derivative) plays a critical role in decoding NNG/A codons and reading frame maintenance during mRNA translation. The lack of this tRNA modification produces a pleiotropic phenotype in bacteria and has been associated with mitochondrial encephalomyopathies in humans. In this work, we use in vitro and in vivo approaches to characterize the enzymatic pathway controlled by the Escherichia coli MnmE*GidA complex. Surprisingly, this complex catalyzes two different GTP- and FAD-dependent reactions, which produce 5-aminomethyluridine and 5-carboxymethylamino-methyluridine using ammonium and glycine, respectively, as substrates. In both reactions, methylene-tetrahydrofolate is the most probable source to form the C5-methylene moiety, whereas NADH is dispensable in vitro unless FAD levels are limiting. Our results allow us to reformulate the bacterial MnmE*GidA dependent pathway and propose a novel mechanism for the modification reactions performed by the MnmE and GidA family proteins.