All bacteria initiate translation using formylated methionine, yet directly after translation, the formyl-group is removed. This sequence of addition and removal appears futile, yet every sequenced bacterial genome encodes the enzymes for formylation and deformylation, suggesting this process is essential. Puzzlingly, the process is absent from both Archaea and Eukaryotes, and moreover, bacterial mutants lacking both the formylase and deformylase activities are viable, albeit with a diminished growth rate. We created an Escherichia coli strain devoid of formylase and deformylase activity. This strain was then allowed to evolve over 1500 generations whereupon it reached wild-type growth rate, demonstrating that formylation can be completely dispensed with. This raises an additional question: if the formylation cycle is unnecessary, how did it emerge and why has it persisted? Our results show that the formylation-deformylation cycle could have evolved as a toxin-antitoxin pair (TA) with post-segregational killing (PSK) activity. TAs ‘addict’ cells to the plasmids that carry them by inducing PSK. We measured the stability of formylase-deformylase encoding plasmids and their ability to elicit PSK in our evolved E. coli strain. We report several lines of evidence consistent with the formylation-cycle having evolved from a plasmid-borne PSK element: 1) in the absence of deformylation, formyl-methionine on proteins is cytotoxic in bacteria 2) deformylation relieves the cytotoxicity of formyl-methionine, 3) the loss of a plasmid containing formylase and deformylase genes from evolved cells results in cessation of growth – a standard PSK phenotype. In addition, we introduced the E. coli formylase and deformylase genes into yeast and demonstrate that Met-tRNA formylation is not lethal, even in the absence of deformylation. This suggests PSK would be ineffectual in yeast, accounting for the absence of formylation from eukaryotic cytoplasmic translation. We also report the presence of formylase and deformylase genes in the two representative members of the archaeal Methanocopusculum genus. Moreover, we demonstrate that these genes have been acquired by a recent horizontal gene transfer from bacteria. Our results indicate that formylmethionine use in bacteria evolved, not through a direct functional benefit to cells, but through competition between infectious genetic elements.