β-methylthiolation is a novel post-translational modification mapping to a universally conserved Asp 88 of the bacterial ribosomal protein S12. This S12 specific modification has been identified on orthologs from multiple bacterial species. The origin and functional significance was investigated with both a proteomic strategy to identify candidate S12 interactors and expression microarrays to search for phenotypes that result from targeted gene knockouts of select candidates. Utilizing an endogenous recombinant E. coli S12 protein with an affinity tag as bait, mass spectrometric analysis identified candidate S12 binding partners including RimO (previously shown to be required for this post-translational modification) and YcaO, a conserved protein of unknown function. Transcriptomic analysis of bacterial strains with deleted genes for RimO and YcaO identified an overlapping transcriptional phenotype suggesting that YcaO and RimO likely share a common function. As a follow up, quantitative mass spectrometry additionally indicated that both proteins dramatically impacted the modification status of S12. Collectively, these results indicate that the YcaO protein is involved in β-methylthiolation of S12 and its absence impairs the ability of RimO to modify S12. Additionally, the proteomic data from this study provides direct evidence that the E. coli specific β-methylthiolation likely occurs when S12 is assembled as part of a ribosomal subunit.