Lys34 of the conserved translation elongation factor P (EF-P) is post-translationally lysinylated by YjeK and YjeA—a modification that is critical for bacterial virulence. Here we show that the currently accepted Escherichia coli EF-P modification pathway is incomplete and lacks a final hydroxylation step mediated by YfcM, an enzyme distinct from deoxyhypusine hydroxylase that catalyzes the final maturation step of eukaryotic initiation factor 5A, the eukaryotic EF-P homolog.