Chlorine-free Platinum/nitrogen-doped graphene oxygen reduction reaction catalysts were synthesized by a one step method of annealing a mixture of platinum acetylacetonate and graphene oxide under ammonia atmosphere. Nanoparticles with close to the ideal particle size for oxygen reduction reaction (ORR) were formed, i.e., with diameter of 3–4 nm (500 and 600 °C) and 6 nm (700 °C). X-ray photoelectron spectroscopy confirmed the successful introduction of both pyridinic and pyrrolic type nitrogen moieties into the graphene layers, which indicates a strong interaction between the nanoparticles and the graphene layers. The electrocatalytic activity of glassy carbon electrodes (GCE) modified with the synthesized Pt/NG samples for oxygen reduction was compared to that of a platinum/carbon black catalyst modified electrode in acidic and alkaline media. Based on the measured limiting current densities and calculated electron transfer number, the highest activity was measured in acidic and alkaline media on the samples annealed at 600 and 700 °C, respectively.