The discharge of dye-colored wastewaters in surface water represents a serious environmental problem because it may decrease the water transparency, therefore having an effect on photosynthesis, and a public health concern because dyes and their reducing products are carcinogenic. In recent years, big achievements have been made in the use of anaerobic granular sludge not only on colored wastewaters but also on the detoxification of other xenobiotics compounds. This paper compiles some important findings related to the potentials of high-temperature anaerobic treatment and redox mediators on the reductive decolorization of azo dyes from textile wastewaters.