Nitrosamines make up a major class of contaminants of emerging concern that are toxic, present at trace levels in aqueous environments, and challenging to destroy because of their chemical stability. We report novel redox electrodes based on hemin-functionalized carbon nanotubes showing high electrocatalytic activity for nitrosamine reduction at low potentials (−0.5 V vs Ag/AgCl or −0.27 vs the standard hydrogen electrode) and with turnover numbers of >700. The redox electrodes were tested under a range of electrolyte and pH conditions and demonstrated high conversion of nitrosamines at high reaction rates, even at parts per billion levels in secondary effluent from a wastewater treatment plant. We propose that the pathway for nitrosamine reduction involves a proton-mediated conversion of the nitroso group to hydrazines and secondary amines. These high-performance biomimetic electrocatalysts for nitrosamine reduction are based on complexes containing earth-abundant metals and, potentially, have broad applications in environmental remediation, water treatment, and industrial organo-electrochemical processes.