Prokaryotes and eukaryotes alike endogenously generate the gaseous molecule hydrogen sulfide (H2S). Bacterial H2S acts as a cytoprotectant against antibiotics-induced stress and promotes redox homeostasis. In E. coli, endogenous H2S production is primarily dependent on 3-mercaptopyruvate sulfurtransferase (3MST), encoded by mstA. Here, we show that cells lacking 3MST acquire a phenotypic suppressor mutation resulting in compensatory H2S production and tolerance to antibiotics and oxidative stress. Using whole genome sequencing, we identified a non-synonymous mutation within an uncharacterized LacI-type transcription factor, ycjW. We then mapped regulatory targets of YcjW and discovered it controls the expression of carbohydrate metabolic genes and thiosulfate sulfurtransferase PspE. Induction of pspE expression in the suppressor strain provides an alternative mechanism for H2S biosynthesis. Our results reveal a complex interaction between carbohydrate metabolism and H2S production in bacteria and the role, a hitherto uncharacterized transcription factor, YcjW, plays in linking the two.