Pt-based catalysts are suffering from the intrinsic high cost and poor stability for practical use in fuel cells. We develop a free-standing fabric type Pt-free high-performance oxygen reduction reaction (ORR) catalyst, consisting of N, Fe-codoped carbon nanofibers and graphene (N/Fe-CG) hybrids. Electrospinning is used to synthesize the free-standing fabric catalysts. Incorporation of graphene into the nanofiber structure greatly increases the electrical conductivity and catalytic surface area. X-ray photoelectron spectroscopy (XPS) analysis provides evidence that Fe-N4 active centers are possibly formed in the catalyst, as is confirmed by electrochemical tests also. Compared to commercial Pt/C, our N/Fe-CG exhibits a similar level of catalytic activity but superior stability and methanol tolerance in both alkaline and acidic media, making it a good candidate for an ORR electrocatalyst in energy storage/conversion and other relevant applications.