Carbon-supported rhenium–palladium catalysts (Re–Pd/C) effectively transform aqueous perchlorate, a widespread drinking water pollutant, via chemical reduction using hydrogen as an electron donor at ambient temperature and pressure. Previous work demonstrated that catalyst activity and stability are heavily dependent on solution composition and Re content in the catalyst. This study relates these parameters to changes in the speciation and molecular structure of Re immobilized on the catalyst. Using X-ray spectroscopy techniques, we show that Re is immobilized as ReVII under oxic solution conditions, but transforms to a mixture of reduced, O-coordinated Re species under reducing solution conditions induced by H2 sparging. Under oxic solution conditions, extended X-ray absorption fine structure (EXAFS) analysis showed that the immobilized ReVII species is indistinguishable from the dissolved tetrahedral perrhenate (ReO4–) anion, suggesting outer-sphere adsorption to the catalyst surface. Under reducing solution conditions, two Re species were identified. At low Re loading (≤1 wt %), monomeric ReI species form in direct contact with Pd nanoclusters. With increased Re loading, speciation gradually shifts to oxidic ReV clusters. The identified Re structures support a revised mechanism for catalytic reduction of ClO4– involving oxygen atom transfer reactions between odd-valence oxorhenium species and the oxyanion (Re oxidation steps) and atomic hydrogen species (Re reduction steps) formed by Pd-catalyzed dissociation of H2.