Ten phenols were selected as natural laccase mediators after screening 44 different compounds with a recalcitrant dye (Reactive Black 5) as a substrate. Their performances were evaluated at different mediator/dye ratios and incubation times (up to 6 h) by the use of Pycnoporus cinnabarinus and Trametes villosa laccases and were compared with those of eight known synthetic mediators (including -NOH- compounds). Among the six types of dyes assayed, only Reactive Blue 38 (phthalocyanine) was resistant to laccase-mediator treatment under the conditions used. Acid Blue 74 (indigoid dye), Reactive Blue 19 (anthraquinoid dye), and Aniline Blue (triarylmethane-type dye) were partially decolorized by the laccases alone, although decolorization was much more efficient and rapid with mediators, whereas Reactive Black 5 (diazo dye) and Azure B (heterocyclic dye) could be decolorized only in the presence of mediators. The efficiency of each natural mediator depended on the type of dye to be treated but, with the only exception being Azure B (< 50% decolorization), nearly complete decolorization (80 to 100%) was attained in all cases. Similar rates were attained with the best synthetic mediators, but the reactions were significantly slower. Phenolic aldehydes, ketones, acids, and esters related to the three lignin units were among the best mediators, including p-coumaric acid, vanillin, acetovanillone, methyl vanillate, and above all, syringaldehyde and acetosyringone. The last two compounds are especially promising as ecofriendly (and potentially cheap) mediators for industrial applications since they provided the highest decolorization rates in only 5 to 30 min, depending on the type of dye to be treated.