The electrical performance of a proton exchange membrane fuel cell is limited by the slow oxygen reduction reaction (ORR) kinetics. Catalytic improvements for the ORR have been obtained on alloyed PtM/C or M-rich-core@Pt-rich-shell/C catalysts (where M is an early or late transition metal) in comparison to pure Pt/C, due to a combination of strain and ligand effects. However, the effect of the fine nanostructure of the nanomaterials on the ORR kinetics remains underinvestigated. Here, nanometer-sized PtNi/C electrocatalysts with low Ni content (∼15 atom %) but different nanostructures and different densities of grain boundary were synthesized: solid, hollow, or “sea sponge” PtNi/C nanoalloys, and solid Ni-core@Pt-shell/C nanoparticles. These nanostructures were characterized by transmission and scanning transmission electron microscopy, X-ray energy dispersive spectroscopy, synchrotron wide-angle X-ray scattering (WAXS), atomic absorption spectroscopy, and electrochemical techniques. Their electrocatalytic activities for the ORR were determined and structure–activity relationships established. The results showed the following: (i) The compression of the Pt lattice by ca. 15 atom % Ni provides mild ORR activity enhancement in comparison to pure Pt/C. (ii) Highly defective PtNi/C nanostructures feature up to 9.3-fold enhancement of the ORR specific activity over a commercial Pt/C material with similar crystallite size. (iii) The enhancement of the ORR kinetics can be ascribed to the presence of structural defects, as shown by two independent parameters: the microstrain determined from WAXS and the average COads electrooxidation potential (μ1 CO) determined from COads stripping measurements. This work indicates that, at fixed Ni content, ORR activity can be tuned by nanostructuring and suggests that targeting structural disorder is a promising approach to improve the electrocatalytic properties of mono- or bimetallic nanocatalysts.