A new biotechnological sequence for decolorizing red and black colored paper was developed to reduce the environmental impact of the chemicals used in paper recycling processes. Commercially available low-redox potential laccase from Myceliophthora thermophila, which operates optimally under alkaline conditions, was used in combination with natural mediators to make the process even greener. Based on the optical properties of the resulting decolorized paper, red and black dyes were efficiently removed by all laccase–mediator systems. The best results were provided by the laccase–methyl syringate combination, followed by the laccase–acetosyringone system and the laccase–syringaldehyde system. The decolorization rate for red paper achieved with the laccase–methyl syringate treatment exceeded that obtained with ozone. Red was removed by about 98% by combining two enzymatic stages and hydrogen peroxide stage, and black by 65%, without altering the physical properties of the colored paper in either case. A sequence combining oxidative and reductive (formamidine sulfinic acid) chemical treatments led to comparable optical and physical properties for the two types of paper. The effects of Myceliophthora thermophila laccase and methyl syringate were similar to those of high-redox potential laccase from Trametes villosa combined with either methyl syringate or the synthetic mediator violuric acid