Synthesis of polyproline proteins leads to translation arrest. To overcome this ribosome stalling effect, bacteria depend on a specialized translation elongation factor P (EF-P), being orthologous and functionally identical to eukaryotic/archaeal elongation factor e/aIF-5A (recently renamed ‘EF5’). EF-P binds to the stalled ribosome between the peptidyl-tRNA binding and tRNA-exiting sites, and stimulates peptidyl-transferase activity, thus allowing translation to resume. In their active form, both EF-P and e/aIF-5A are post-translationally modified at a positively charged residue, which protrudes toward the peptidyl-transferase center when bound to the ribosome. While archaeal and eukaryotic IF-5A strictly depend on (deoxy-) hypusination (hypusinylation) of a conserved lysine, bacteria have evolved diverse analogous modification strategies to activate EF-P. In Escherichia coli and Salmonella enterica a lysine is extended by β-lysinylation and subsequently hydroxylated, whereas in Pseudomonas aeruginosa and Shewanella oneidensis an arginine in the equivalent position is rhamnosylated. Inactivation of EF-P, or the corresponding modification systems, reduces not only bacterial fitness, but also impairs virulence. Here, we review the function of EF-P and IF-5A and their unusual posttranslational protein modifications.