Implementing parts per billion-level nitric oxide (NO) sensing at room temperature (RT) is still in extreme demand for monitoring inflammatory respiratory diseases. Herein, we have prepared a kind of core-shell structural Hemin-based nanospheres (Abbr.: Hemin-nanospheres, defined as HNSs) with the core of amorphous Hemin and the shell of acetone-derived carbonized polymer, whose core-shell structure was verified by XPS with argon-ion etching. Then, the HNS-assembled reduced graphene oxide composite (defined as HNS-rGO) was prepared for RT NO sensing. The acetone-derived carbonized polymer shell not only assists the formation of amorphous Hemin core by disrupting their crystallization to release more Fe-N4 active sites, but provides protection to the core. Owing to the unique core-shell structure, the obtained HNS-rGO based sensor exhibited superior RT gas sensing properties toward NO, including a relatively higher response (Ra/Rg = 5.8, 20 ppm), a lower practical limit of detection (100 ppb), relatively reliable repeatability (over 6 cycles), excellent selectivity, and much higher long-term stability (less than a 5% decrease over 120 days). The sensing mechanism has also been proposed based on charge transfer theory. The superior gas sensing properties of HNS-rGO are ascribed to the more Fe-N4 active sites available under the amorphous state of the Hemin core and to the physical protection by the shell of acetone-derived carbonized polymer. This work presents a facile strategy of constructing a high-performance carbon-based core-shell nanostructure for gas sensing.