The slow rate of the oxygen reduction reaction (ORR) in the polymer electrolyte membrane fuel cell (PEMFC) is the main limitation for automotive applications. We demonstrated that the Pt3Ni(111) surface is 10-fold more active for the ORR than the corresponding Pt(111) surface and 90-fold more active than the current state-of-the-art Pt/C catalysts for PEMFC. The Pt3Ni(111) surface has an unusual electronic structure (d-band center position) and arrangement of surface atoms in the near-surface region. Under operating conditions relevant to fuel cells, its near-surface layer exhibits a highly structured compositional oscillation in the outermost and third layers, which are Pt-rich, and in the second atomic layer, which is Ni-rich. The weak interaction between the Pt surface atoms and nonreactive oxygenated species increases the number of active sites for O2 adsorption.