As organic dyes are a major source of pollution, it is important to develop novel and efficient heterogeneous catalysts with high activity for their degradation. In this work, two innovative techniques, atomic layer deposition and electrospinning, were used to prepare palladium nanoparticles (Pd NPs) supported on carbon nanofibers (CNFs). The sample morphology was investigated using scanning and transmission electron microscopy. This showed the presence of nanofibers of several micrometers in length and with a mean diameter of 200 nm. Moreover, the size of the highly dispersed Pd NPs was about 7 nm. X-ray photoelectron spectroscopy visually validated the inclusion of metallic Pd. The prepared nano-catalysts were then used to reduce methyl orange (MO) in the presence of sodium borohydride (NaBH4). The Freundlich isotherm model was the most suitable model to explain the adsorption equilibrium for MO onto the Pd/CNF catalysts. Using 5 mL MO dye-solution (0.0305 mM) and 1 mL NaBH4 (0.026 mM), a 98.9% of catalytic activity was achieved in 240 min by 0.01 g of the prepared nano-catalysts Pd/C (0.016 M). Finally, no loss of catalytic activity was observed when such catalysts were used again. These results represent a promising avenue for the degradation of organic pollutants and for heterogeneous catalysis.