We present the synthesis of palladium nanocrystals self-assembled on helical carbon nanofibers functionalized with benzyl mercaptan (Pd-S-HCNFs) and their electrocatalytic activity toward the oxidation of formic acid, methanol and ethanol. Helical carbon nanofibers (HCNFs) were first functionalized with benzyl mercaptan based on the pi-pi interactions between phenyl rings and the graphitic surface of HCNFs. Palladium nano crystals (PdNC) were fixed on the surface of functionalized HCNF by Pd-S bonds in a simple self-assembly method. The as-prepared materials were characterized by high resolution transmission electron microscopy (HR-TEM), X-ray photoelectron spectroscopy (XPS) and X-ray diffraction (XRD), energy dispersive X-ray spectroscopy (EDX), cyclic voltammetry (CV), and fuel cell tests. CV characterization of the as-prepared materials shows a very high electrocatalytic activity for oxidation of formic acid, ethanol and methanol in strong alkaline electrolyte. In comparison to commercial catalyst Vulcan XC-72 decorated with Pd nanoparticles, the proposed Pd-S-HCNFs nano composite material shows oxidation currents for formic acid, ethanol and methanol at the Pd-S-HCNF-modified electrode that are higher than that at the Pd/XC-72 modified electrode with a factor of 2.0, 1.5, and 2.3, respectively. In a formic acid fuel cell the Pd-S-HCNF modified electrode yields equal power density as commercial Pd/XC-72 catalyst. Our results show that Pd-decorated helical carbon nanofibers with diameters around 40-60 nm have very high potential as active material in fuel cells, electrocatalysts and sensors.