Considerable effort has been devoted recently to replace platinum-based catalysts with their non-noble-metal counterparts in the oxygen reduction reaction (ORR) in fuel cells. Nitrogen-doped carbon structures emerged as possible candidates for this role, and their earth-abundant metal-decorated composites showed great promise. Here, we report on the simultaneous formation of nitrogen-doped graphene and iron nitride from the lyophilized mixture of graphene oxide and iron salt by high-temperature annealing in ammonia atmosphere. A mixture of FeN and Fe2N particles was formed with average particle size increasing from 23.4 to 127.0 nm and iron content ranging from 5 to 50 wt %. The electrocatalytic oxygen reduction activity was investigated via the rotating disk electrode method in alkaline media. The highest current density of 3.65 mA cm-2 at 1500 rpm rotation rate was achieved in the 20 wt % catalyst via the four-electrode reduction pathway, exceeding the activity of both the pristine iron nitride and the undecorated nitrogen-doped graphene. Since our catalysts showed improved methanol tolerance compared to the platinum-based ones, the formed non-noble-metal system offers a viable alternative to the platinum-decorated carbon black (Pt/CB) ORR catalysts in direct methanol fuel cells.