Nanostructured C-based catalysts have been developed to be used in continuously operated (open-flow) reactors for the removal of bromates and nitrates from polluted water. The catalysts contain transition-metal (Pd, Cu, and Sn) nanoparticles (NPs) supported on activated carbon fiber fabrics, honeycomb monoliths, and sintered metal fiber (SMF) filters coated by carbon nanofibers (CNF). All catalysts were effective in the reduction of nitrates and bromates present in polluted natural and industrial waters. The best results for nitrate removal in terms of selectivity to N-2 were obtained with the NPs of Pd-Sn (2:1) supported on a mesoporous 5% CNF/SMF. In bromate removal, the same 5% CNF/SMF support with monometallic Pd-0 NPs showed the highest performance because of suppressed mass-transport limitations. Finally, the (0.3% Pd + 0.15% Sn)/5% CNF/SMF catalyst was tested in simultaneous bromate and nitrate removal from synthetic polluted waters and shown to be suitable for attaining pollutant concentrations below the legislation limits (SO mg/L for nitrates and 10 mu g/L for bromates since 2009 in Europe). The continuously operated reactor designed as a bubble column staged with two different types of the fibrous catalysts has been proposed for the simultaneous bromate and nitrate removal from polluted waters.