The metabolic network for sulfide assimilation and trafficking in methanogens is largely unknown. To discover novel proteins required for these processes, bioinformatic methods were used to identify genes co-occurring with the protein biosynthesis enzyme SepCysS, which converts phosphoseryl-tRNACys to cysteinyl-tRNACys in nearly all methanogens. The analyses revealed three conserved protein-coding genes, each containing molecular signatures predicting functions in sulfur metabolism. All three genes were also identified in more than 50 strictly anaerobic bacterial genera from nine distinct phyla.