Azo dyes are widespread pollutants and potential cocontaminants for nitrate; we evaluated their effect on catalytic reduction of a suite of oxyanions, diatrizoate, and N-nitrosodimethylamine (NDMA). The azo dye methyl orange significantly enhanced (less than or equal to a factor of 5.24) the catalytic reduction kinetics of nitrate, nitrite, bromate, perchlorate, chlorate, and diatrizoate with several different Pd-based catalysts; NDMA reduction was not enhanced. Nitrate was selected as a probe contaminant, and a variety of azo dyes (methyl orange, methyl red, fast yellow AB, metanil yellow, acid orange 7, congo red, eriochrome black T, acid red 27, acid yellow 11, and acid yellow 17) were evaluated for their ability to enhance reduction. Hydrogenation energies of azo dyes were calculated using density functional theory and a volcano relationship between hydrogenation energies and reduction rate enhancement was observed. A kinetic model based on Brønsted-Evans-Polanyi (BEP) theory matched the volcano relationship and suggests sorbed azo dyes enhance reduction kinetics through hydrogen atom shuttling between reduced azo dyes (i.e., hydrazo dyes) and oxyanions or diatrizoate. This is the first research that has identified this synergetic effect, and it has implications for designing more efficient catalysts and reducing Pd costs in water treatment systems.