Pyrogenic carbonaceous matter (PCM) catalyzes the transformation of a range of organic pollutants by sulfide in water; however, the mediation mechanisms are not fully understood. In this study, we observed for the first time that the degradation of azo dyes by sulfide initially underwent a lag phase followed by a fast degradation phase. Interestingly, the presence of PCM only reduced the lag phase length of the azo dye decolorization but did not significantly enhance the reaction rate in the fast degradation phase. An analysis of the azo dye reduction and polysulfide formation indicated that PCM facilitated the transformation of sulfide into polysulfides, including disulfide and trisulfide, resulting in fast azo dye reduction. Moreover, the oxygen functional groups of the PCM, especially the quinones, may play an important role in the transformation of sulfide into polysulfides by accelerating the electron transfer. The results of this study provide a better understanding of the PCM-mediated abiotic transformation of organic pollutants by sulfide in anaerobic aqueous environments.