Concentrated sodium chloride (NaCl) brines are often used to regenerate ion-exchange (IX) resins applied to treat drinking water sources contaminated with perchlorate (ClO4−), generating large volumes of contaminated waste brine. Chemical and biological processes for ClO4− reduction are often inhibited severely by high salt levels, making it difficult to recycle waste brines. Recent work demonstrated that novel rhenium–palladium bimetallic catalysts on activated carbon support (Re–Pd/C) can efficiently reduce ClO4− to chloride (Cl−) under acidic conditions, and here the applicability of the process for treating waste IX brines was examined. Experiments conducted in synthetic NaCl-only brine (6–12 wt%) showed higher Re–Pd/C catalyst activity than in comparable freshwater solutions, but the rate constant for ClO4− reduction measured in a real IX waste brine was found to be 65 times lower than in the synthetic NaCl brine. Through a series of experiments, co-contamination of the IX waste brine by excess NO3− (which the catalyst reduces principally to NH4+) was found to be the primary cause for deactivation of the Re–Pd/C catalyst, most likely by altering the immobilized Re component. Pre-treatment of NO3− using a different bimetallic catalyst (In–Pd/Al2O3) improved selectivity for N2 over NH4+ and enabled facile ClO4− reduction by the Re–Pd/C catalyst. Thus, sequential catalytic treatment may be a promising strategy for enabling reuse of waste IX brine containing NO3− and ClO4−.