Ribosomal protein S12 undergoes a unique posttranslational modification, methylthiolation of residue D88, in Escherichia coli and several other bacteria. Using mass spectrometry, we have identified the enzyme responsible for this modification in E. coli, the yliG gene product. This enzyme, which we propose be called RimO, is a radical-S-adenosylmethionine protein that bears strong sequence similarity to MiaB, which methylthiolates tRNA. We show that RimO and MiaB represent two of four subgroups of a larger, ancient family of likely methylthiotransferases, the other two of which are typified by Bacillus subtilis YqeV and Methanococcus jannaschii Mj0867, and we predict that RimO is unique among these subgroups in its modification of protein as opposed to tRNA. Despite this, RimO has not significantly diverged from the other three subgroups at the sequence level even within the C-terminal TRAM domain, which in the methyltransferase RumA is known to bind the RNA substrate and which we presume to be responsible for substrate binding and recognition in all four subgroups of methylthiotransferases. To our knowledge, RimO and MiaB represent the most extreme known case of resemblance between enzymes modifying protein and nucleic acid. The initial results presented here constitute a bioinformatics-driven prediction with preliminary experimental validation that should serve as the starting point for several interesting lines of further inquiry.