Ribosome stalling at polyproline stretches is common and fundamental. In bacteria, translation elongation factor P (EF-P) rescues such stalled ribosomes, but only when it is post-translationally activated. In Escherichia coli, activation of EF-P is achieved by (R)-β-lysinylation and hydroxylation of a conserved lysine. Here we have unveiled a markedly different modification strategy in which a conserved arginine of EF-P is rhamnosylated by a glycosyltransferase (EarP) using dTDP-L-rhamnose as a substrate. This is to our knowledge the first report of N-linked protein glycosylation on arginine in bacteria and the first example in which a glycosylated side chain of a translation elongation factor is essential for function. Arginine-rhamnosylation of EF-P also occurs in clinically relevant bacteria such as Pseudomonas aeruginosa. We demonstrate that the modification is needed to develop pathogenicity, making EarP and dTDP-L-rhamnose-biosynthesizing enzymes ideal targets for antibiotic development.