Concentrated sodium chloride (NaCl) brines are often used to regenerate ion-exchange (IX) resins applied to treat drinking water sources contaminated with perchlorate (ClO 4 − ), generating large volumes of contaminated waste brine. Chemical and biological processes for ClO 4 − 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 ClO 4 − 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 ClO 4 − 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 NO 3 − (which the catalyst reduces principally to NH 4 + ) 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 NO 3 − using a different bimetallic catalyst (In–Pd/Al 2 O 3 ) improved selectivity for N 2 over NH 4 + and enabled facile ClO 4 − reduction by the Re–Pd/C catalyst. Thus, sequential catalytic treatment may be a promising strategy for enabling reuse of waste IX brine containing NO 3 − and ClO 4 − .