An extremely efficient ethanol fuel cell electrode is produced by combining the large surface area of vertically oriented and highly conductive few-layer graphene sheets with electrochemically deposited palladium nanoparticles. The electrodes show an extraordinary high catalyst activity of up to 7977 mA/(mg Pd) at low catalyst loadings of 0.64 μg/cm2 and a very high current density of up to 106 mA/cm2 at high catalyst loadings of 83 μg/cm2. Moreover, the low onset potentials combined with a good poisoning resistance and long-term stability make these electrodes highly suitable for real applications. These features are achieved by using a newly developed electrochemical catalyst deposition process exploiting high voltages of up to 3.5 kV. This technique allows controlling the catalyst amount ranging from a homogeneous widespread distribution of small (≤10 nm) palladium nanoparticles to rather dense layers of particles, while every catalyst particle has electrical contact to the graphene electrode.