The growing demands for reagentless hydrogen peroxide (H2O2) and β-nicotinamide adenine dinucleotide (β-NADH) sensors from food, pharmaceutical, chemical, and biochemical fields have stimulated extensive research interest on nano-engineered Pd. In this paper, Pd/carbon composite nanofibers were prepared by electrodepositing Pd onto electrospun carbon nanofibers to act as a catalyst toward the electrocatalytic redox reactions of H2O2 and β-NADH. The morphology of nano-engineered Pd was controlled by selectively adjusting the electrodeposition time and potential. Scanning electron microscopy and transmission electron microscopy results showed that nanocactus- and nanoflower-like Pd depositions were obtained on the surface of carbon nanofibers. Electrocatalytic analysis demonstrated a high electrocatalytic activity of the composite nanofibers for the redox of H2O2 and oxidation of β-NADH.