It is a great challenge to develop efficient room-temperature sensing materials and sensors for nitric oxide (NO) gas, which is a biomarker molecule used in the monitoring of inflammatory respiratory diseases. Herein, Hemin (Fe (III)-protoporphyrin IX) is introduced into the nitrogen-doped reduced graphene oxide (N-rGO) to obtain a novel sensing material HNG-ethanol. Detailed XPS spectra and DFT calculations confirm the formation of carbon-iron bonds in HNG-ethanol during synthesis process, which act as electron transport channels from graphene to Hemin. Owing to this unique chemical structure, HNG-ethanol exhibits superior gas sensing properties toward NO gas (R a /R g = 3.05, 20 ppm) with a practical limit of detection (LOD) of 500 ppb and reliable repeatability (over 5 cycles). The HNG-ethanol sensor also possesses high selectivity against other exhaled gases, high humidity resistance, and stability (less than 3% decrease over 30 days). In addition, a deep understanding of the gas sensing mechanisms is proposed for the first time in this work, which is instructive to the community for fabricating sensing materials based on graphene-iron derivatives in the future.