Perchlorate (ClO4-) is a pervasive, harmful, and inert anion on both Earth and Mars. Current technologies for ClO4- reduction entail either harsh conditions or multicomponent enzymatic processes. Herein, we report a heterogeneous (L)Mo-Pd/C catalyst directly prepared from Na2MoO4, a bidentate nitrogen ligand (L), and Pd/C to reduce aqueous ClO4- into Cl- with 1 atm of H2 at room temperature. A suite of instrument characterizations and probing reactions suggest that the MoVI precursor and L at the optimal 1:1 ratio are transformed in situ into oligomeric MoIV active sites at the carbon-water interface. For each Mo site, the initial turnover frequency (TOF0) for oxygen atom transfer from ClOx- substrates reached 165 h-1. The turnover number (TON) reached 3840 after a single batch reduction of 100 mM ClO4-. This study provides a water-compatible, efficient, and robust catalyst to degrade and utilize ClO4- for water purification and space exploration.