The electrochemical stability and catalytic activity of 20 wt. % Pd-CeO_2-NR/C (Pd:CeO_2-NR 1:1 atomic ratio) and 20 wt. % Pd/C nanocatalysts for the Oxygen Reduction Reaction (ORR) and the Ethanol Oxidation Reaction (EOR) in 0.5 mol L^-1 KOH is evaluated in this work. The nanocatalysts have been synthesized by the polyol method. The morphology and chemical composition of the synthesized Pd-CeO_2-NR/C and Pd/C have been determined in a Field Emission Scanning Electron Microscope (FESEM) with an energy dispersive X-Ray detector. The results show a chemical composition close to the nominally expected. Meanwhile, the XRD analysis demonstrates the crystalline nature of the nanocatalysts with crystallite size of Pd-CeO_2-NR/C and Pd/C of 11.8 and 7.9 nm, respectively. XPS analysis indicates mainly the presence of Pd⁰, Pd²⁺, and Pd⁴⁺ species on both electrocatalyst, as well as Ce³⁺ and Ce⁴⁺ in Pd-CeO_2-NR/C. It has been determined that after accelerated degradation test (ADT, 3000 cycles between 0.6 and 1.0 V/RHE), the ECSA loss of Pd-CeO_2-NR/C is of around 3 %, clearly smaller compared to 80 % in the case of Pd/C, which suggests a synergic effect between CeO_2-NR and Pd that stabilizes the metallic nanoparticles. Evaluation by RRDE shows that Pd-CeO_2-NR/C has a catalytic activity for the ORR similar to Pd/C in terms of onset potential of the ORR (0.98 and 0.94 V/RHE before ADT, respectively; 0.91 and 0.92 V/RHE after ADT, respectively). Nevertheless, Pd-CeO_2-NR/C delivers higher mass and specific activities than Pd/C, with both nanocatalysts producing about the same amount of H₂O₂ (around 3 - 4.5 %). Meanwhile, the polarization curves of the EOR before ADT show a peak mass current density of 697.70 mA mg_Pd^-1 generated by Pd-CeO_2-NR/C (at 0.86 V/RHE), higher than 665.66 mA mg_Pd^-1 obtained from Pd/C (at 0.92 V/RHE). After ADT, the mass current density increased by 1.6 and 1.4 times at Pd-CeO_2-NR/C and Pd/C, respectively. The results show that Pd-CeO_2-NR/C is a highly electrochemically stable bifunctional nanocatalysts with high catalytic activity for the ORR and the EOR in alkaline media, which make it a promising candidate for A-DEFCs applications.