For palladium nanocatalysts (PdNCs) to be used as a successfully high-performance direct ethanol fuel cell anode material, improvements in electro-catalytic activity and stability are needed. Here we show an excellent controllable electrodeposition method for fabricating the ultraporous structure of PdNCs. Ultraporous PdNCs were coated on three different carbon materials: flexible carbon fiber paper (CFP), and CFP modified with either graphene oxide (GO) or reduced graphene oxide (rGO) nanosheets. The as-fabricated electrode of PdNCs/rGO/CFP exhibits higher catalytic activity toward the electro-oxidation of ethanol in alkaline media, more excellent poisoning tolerance to carbonaceous species, and higher stability than other electrodes.