We present a procedure to produce single-phase PdP2 nanocrystals (NCs). The approach involves the reaction of palladium(II) acetylacetonate and hexamethylphosphoroustriamide to nucleate defective Pd5P2 nanoparticles that subsequently, with further phosphorous incorporation, crystallize into PdP2. The synthesized PdP2 NCs were supported on reduced graphene oxide (rGO) and applied as electrocatalysts for ethanol oxidation. The activity of PdP2 toward the ethanol oxidation reaction (EOR) was over a threefold higher than that of Pd NCs prepared under similar conditions. Even better performance was obtained from PdP2 NCs supported on rGO, which showed current densities up to 51.4 mA cm−2 and mass activities of 1.60 A mg-1Pd, that is 4.8 and 15 times higher than Pd NCs. Besides, PdP2 NCs and PdP2/rGO catalysts showed improved stability during EOR than Pd NCs and Pd/rGO.