Mass-selected platinum–gadolinium alloy nanoparticles (PtxGd NPs) are synthesized for the first time as oxygen reduction reaction (ORR) electrocatalysts using the gas aggregation technique, under ultrahigh vacuum (UHV) conditions. The morphology of the PtxGd catalysts is characterized, and their catalytic performance toward the ORR is assessed in acidic media using a half-cell configuration. The PtxGd 8-nm catalyst shows a high activity (3.6 A (mg Pt)−1), surpassing the highest activity reached so far with PtxY NP catalysts. In addition, the optimum PtxGd catalyst also presents high stability, as suggested by the accelerated stability tests under ORR potential cycling. Extended X-ray absorption fine structure (EXAFS) spectroscopy measurements confirm that as-prepared PtxGd NPs are compressively strained, relative to pure Pt, and that a PtxGd core/Pt-rich shell structure is adopted after partial Gd leaching. The activity correlates strongly with the compressive strain. On that basis, we propose that the ORR enhancement is due to the compressive strain within the Pt shell induced by the alloy core. The results herein confirm the suitability of PtxGd NPs as cathode nanocatalysts for proton exchange membrane fuel cells (PEMFCs).