A novel VN/C nanostructure consisting of VN nanoparticles and graphite-dominant carbon layers is synthesized by nitridation of V2O5 using melamine as reductant under inert atmosphere. High crystalline VN nanoparticles are observed to be uniformly distributed in carbon layers with an average size of ca13.45 nm. Moreover, the electrocatalytic performance of VN/C towards oxygen reduction reaction (ORR) in alkaline electrolyte is fascinating. The results show that VN/C has a considerable ORR activity, including a 75 percent value of the diffusion-limited current density and a 0.11 V smaller value about the onset potential with respect to Pt/C catalyst. Moreover, the excellent methanol-tolerance performance of VN/C has also been verified with 3 M methanol. Combined with the competitive prices, this VN/C nanocomposite can serve as an appropriate non-precious methanol-tolerant ORR catalyst for alkaline fuel cells.