New PdP cathodes with 10 at.% P (PdP10) as catalysts for the oxygen reduction reaction (ORR) were prepared by using different electroless deposition times onto a carbon paper and compared to PdP15, Pd and Pt. The as-prepared electrodes were characterized by SEM, XRD, TEM/SAED and XPS. The electrochemical activity was evaluated using CO stripping, cyclic and linear sweep voltammetry and rotating disk electrode in acid media in the presence, and in the absence of methanol. It is shown that the PdP10 and PdP15 are mainly composed of nanocrystals aggregated as spherical nanoparticles, dispersed in an amorphous matrix. The electrochemical testing showed that hydrogen absorption and the CO tolerance of PdP10 is higher than for PdP15. ORR proceeded via the 4-electron pathway on both catalysts. PdP10 presented the highest ORR mass activity together with a high methanol tolerance. At the end of the accelerated stability test, the mass activity of PdP10 for the ORR increased by about 30%, whereas the at.% P remained the same. The improved performance was explained by atomic rearrangement, the initial spherical-type nanoparticles becoming 3D tree-like dendrites with increased particle size. The PdP10 was tested as the cathode catalyst in a single polymer electrolyte fuel cell (PEMFC), achieving a mass activity of 1.75 A mgPd-1 at 0.5 V and 60 °C, which is in the superior range of performance of PEMFCs without Pt at the cathode.