Gentamicin is an important aminoglycoside antibiotic used for treatment of infections caused by Gram-negative bacteria. Although most of the biosynthetic pathways of gentamicin have been elucidated, a remaining intriguing question is how the intermediates JI-20A and JI-20B undergo a dideoxygenation to form gentamicin C complex. Here we show that the dideoxygenation process starts with GenP-catalyzed phosphorylation of JI-20A and JI-20Ba. The phosphorylated products are successively modified by concerted actions of two PLP (pyridoxal 5′-phosphate)-dependent enzymes: elimination of water and then phosphate by GenB3 and double bond migration by GenB4. Each of these reactions liberates an imine which hydrolyses to a ketone or aldehyde and is then reaminated by GenB3 using an amino donor. Importantly, crystal structures of GenB3 and GenB4 have guided site-directed mutagenesis to reveal crucial residues for the enzymes’ functions. We propose catalytic mechanisms for GenB3 and GenB4, which shed light on the already unrivalled catalytic versatility of PLP-dependent enzymes.