Pd nanoparticles (Pd NPs) on a carbon support (Pd/C) were synthesized in ethylene glycol containing poly(1-vinyl- 2-pyrrolidone) (PVP) at various PVP/Pd precursor ratios. The sizes of the Pd NPs were controlled by varying the PVP concentration. Smaller Pd NPs were obtained at higher PVP concentrations. Indeed, the mean sizes of the Pd NPs with PVP/Pd precursor ratios of 0, 40, and 80 (Pd/C-0, -40, and -80) were 2.8 (±1.2), 1.5 (±0.3), and 0.8 (±0.3) nm, respectively, by TEM analysis. The electrocatalytic activities of the Pd/C catalysts toward the oxygen reduction reaction (ORR) were examined in a 0.1M HClO4 solution using rotating disk electrode voltammetry. The smaller Pd NPs exhibited more efficient ORR properties, such as a more positive ORR onset potential (or half-wave potential, E1/2) and increased number of electrons (n) transferred in the ORR. In particular, the Pd/C-80 catalyst with a lower metal content (7.9 wt% Pd) showed desirable ORR performance in terms of the onset potential, n value, mass activity, and methanol tolerance.