Rapid reduction of aqueous ClO4– to Cl– by H2 has been realized by a heterogeneous Re(hoz)2–Pd/C catalyst integrating Re(O)(hoz)2Cl complex (hoz = oxazolinyl-phenolato bidentate ligand) and Pd nanoparticles on carbon support, but ClOx– intermediates formed during reactions with concentrated ClO4– promote irreversible Re complex decomposition and catalyst deactivation. The original catalyst design mimics the microbial ClO4– reductase, which integrates Mo(MGD)2 complex (MGD = molybdopterin guanine dinucleotide) for oxygen atom transfer (OAT). Perchlorate-reducing microorganisms employ a separate enzyme, chlorite dismutase, to prevent accumulation of the destructive ClO2– intermediate. The structural intricacy of MGD ligand and the two-enzyme mechanism for microbial ClO4– reduction inspired us to improve catalyst stability by rationally tuning Re ligand structure and adding a ClOx– scavenger. Two new Re complexes, Re(O)(htz)2Cl and Re(O)(hoz)(htz)Cl (htz = thiazolinyl-phenolato bidentate ligand), significantly mitigate Re complex decomposition by slightly lowering the OAT activity when immobilized in Pd/C. Further stability enhancement is then obtained by switching the nanoparticles from Pd to Rh, which exhibits high reactivity with ClOx– intermediates and thus prevents their deactivating reaction with the Re complex. Compared to Re(hoz)2–Pd/C, the new Re(hoz)(htz)–Rh/C catalyst exhibits similar ClO4– reduction activity but superior stability, evidenced by a decrease of Re leaching from 37% to 0.25% and stability of surface Re speciation following the treatment of a concentrated “challenge” solution containing 1000 ppm of ClO4–. This work demonstrates the pivotal roles of coordination chemistry control and tuning of individual catalyst components for achieving both high activity and stability in environmental catalyst applications.