Ba-Nb-O-N/carbon black (CB), Ba-Zr-O-N/CB, and Ba-Nb-Zr-O-N/CB catalysts were prepared by a polymerized complex method and subsequent nitridation under ammonia flow and were investigated as cathode catalysts for the oxygen reduction reaction (ORR) in polymer electrolyte fuel cells (PEFCs). These catalysts were characterized by X-ray diffraction, transmission electron microscopy, and X-ray photoelectron spectroscopy. The catalytic activity of the prepared catalysts for the ORR and the formation of H2O2 were evaluated by voltammetry using a static electrode and a rotating ring-disk electrode, respectively, in an O-2-saturated 0.1 M H2SO4 solution at room temperature. The results showed that oxygen reduction on the three catalysts proceeds mostly via a four-electron transfer reaction to water and that the two-electron pathway to the H2O2 formation amounted to less than 12%. The Ba-Nb-Zr-O-N/CB catalyst showed the highest ORR activity probably because of Zr-related active sites, which were Zr sites modified by the presence of nearby heteroelements, such as Ba and Nb5+.