A biomimetic heterogeneous catalyst combining palladium nanoparticles and an organic ligand-coordinated oxorhenium complex on activated carbon, Re(hoz)2–Pd/C, was previously developed and shown to reduce aqueous perchlorate (ClO4–) with H2 at a rate ∼100 times faster than the first generation ReOx–Pd/C catalyst prepared from perrhenate (ReO4–). However, the immobilized Re(hoz)2 complex was shown to partially decompose and leach into water as ReO4–, leading to an irreversible loss of catalytic activity. In this work, the stability of the immobilized Re(hoz)2 complex is shown to depend on kinetic competition between three processes: (1) ReV(hoz)2 oxidation by ClO4– and its reduction intermediates ClOx–, (2) ReVII(hoz)2 reduction by Pd-activated hydrogen, and (3) hydrolytic ReVII(hoz)2 decomposition. When ReV(hoz)2 oxidation is faster than ReVII(hoz)2 reduction, the ReVII(hoz)2 concentration builds up and leads to hydrolytic decomposition to ReO4– and free hoz ligand. Rapid ReV(hoz)2 oxidation is mainly promoted by highly reactive ClOx– formed from the reduction of ClO4–. To mitigate Re(hoz)2 decomposition and preserve catalytic activity, ruthenium (Ru) and rhodium (Rh) were evaluated as alternative H2 activators to Pd. Rh showed superior activity for reducing the ClO3– intermediate to Cl–, thereby preventing ClOx– buildup and lowering Re complex decomposition in the Re(hoz)2–Rh/C catalyst. In contrast, Ru showed the lowest ClO3– reduction activity and resulted in the most Re(hoz)2 decomposition among the Re(hoz)2–M/C catalysts. This work highlights the importance of using mechanistic insights from kinetic and spectroscopic tests to rationally design water treatment catalysts for enhanced performance and stability.