Few layer graphene (FLG), multi-walled carbon nanotubes (CNTs) and a nanotube-graphene composite (CNT-FLG) were used as supports for palladium nanoparticles. The catalysts, which were characterized by transmission electron microscopy, Raman spectroscopy and X-ray diffraction, were used as anodes in the electrooxidation of ethanol, ethylene glycol and glycerol in half cells and in passive direct ethanol fuel cells. Upon Pd deposition, a stronger interaction was found to occur between the metal and the nanotube-graphene composite and the particle size was significantly smaller in this material (6.3 nm), comparing with nanotubes and graphene alone (8 and 8.4 nm, respectively). Cyclic voltammetry experiments conducted with Pd/CNT, Pd/FLG and Pd/CNT-FLG in 10 wt% ethanol and 2 M KOH solution, showed high specific currents of 1.48,2.29 and 2.51 mA·µg−1Pd, respectively. Moreover, the results obtained for ethylene glycol and glycerol oxidation highlighted the excellent electrocatalytic activity of Pd/CNT-FLG in terms of peak current density (up to 3.70 mA·µg−1Pd for ethylene glycol and 1.84 mA·μg−1Pd for glycerol, respectively). Accordingly, Pd/CNT-FLG can be considered as the best performing one among the electrocatalysts ever reported for ethylene glycol oxidation, especially considering the low metal loading used in this work. Direct ethanol fuel cells at room temperature were studied by obtaining power density curves and undertaking galvanostatic experiments. The power density outputs using Pd/CNT, Pd/FLG and Pd/CNT-FLG were 12.1, 16.3 and 18.4 mW·cm−2, respectively. A remarkable activity for ethanol electrooxidation was shown by Pd/CNT-FLG anode catalyst. In a constant current experiment, the direct ethanol fuel cell containing Pd/CNT-FLG could continuously deliver 20 mA·cm−2 for 9.5 h during the conversion of ethanol into acetate of 30%, and the energy released from the cell was about 574 J.