Hydroxide-exchange membrane fuel cells can potentially utilize platinum-group-metal (PGM)-free electrocatalysts, offering cost and scalability advantages over more developed proton-exchange membrane fuel cells. However, there is a lack of non-precious electrocatalysts that are active and stable for the hydrogen oxidation reaction (HOR) relevant to hydroxide-exchange membrane fuel cells. Here we report the discovery and development of Ni3N as an active and robust HOR catalyst in alkaline medium. A supported version of the catalyst, Ni3N/C, exhibits by far the highest mass activity and break-down potential for a PGM-free catalyst. The catalyst also exhibits Pt-like activity for hydrogen evolution reaction (HER) in alkaline medium. Spectroscopy data reveal a downshift of the Ni d band going from Ni to Ni3N and interfacial charge transfer from Ni3N to the carbon support. These properties weaken the binding energy of hydrogen and oxygen species, resulting in remarkable HOR activity and stability.