This study reports the preparation, characterization, and electrocatalytic properties of palladium-based catalysts containing ceria (CeO2) on carbon black (CB) and onion-like carbon (OLC) supports. The electrocatalysts (Pd–CeO2/CB and Pd–CeO2/OLC) exhibit a large specific surface area, pore volume, and small particle size, as well as enhanced interfacial interaction and synergy among Pd, CeO2, and OLC in Pd–CeO2/OLC that are valuable for improved electrocatalysis. The presence of CeO2 in Pd–CeO2/OLC induces ca. 7% defects and modifies the electronic structure of the Pd/OLC interface, significantly improving the electrical conductivity due to enhanced charge redistribution, corroborated by density functional theory (DFT) calculations. Pd–CeO2/OLC displays the lowest adsorption energies (H*, OH*, and OOH*) among the series. For the hydrogen oxidation reaction (HOR), Pd–CeO2/OLC delivers significantly enhanced HOR (mass-specific) activities of 4.2 (8.1), 13.2 (29.6), and 15 (78.5) times more than Pd–CeO2/CB, Pd/OLC, and Pd/CB, respectively, with the best diffusion coefficient (D) and heterogeneous rate constant (k). Pd–CeO2/OLC also displays less degradation during accelerated durability testing. In an anion-exchange-membrane fuel cell (AEMFC) with H2 fuel, Pd–CeO2/OLC achieved the highest peak power density of 1.0 W cm–2 at 3.0 A cm–2 as compared to Pd–CeO2/CB (0.9 W cm–2 at 2.2 A cm–2), Pd/OLC (0.6 W cm–2 at 1.7 A cm–2), and Pd/CB (0.05 W cm–2 at 0.1 A cm–2). These results indicate that Pd–CeO2/OLC promises to serve as a high-performing and durable anode material for AEMFCs.