Sensitivity of Fe-decorated graphene with three different graphene-based supports (single vacancy, double vacancy and four nitrogen decorated) toward toxic gas CO and NO has been investigated by first-principles density functional theory (DFT) calculations. The adsorption configuration, adsorption energy, charge transfer, density of states, competitive behaviors of CO and NO on Fe/GN are thoroughly discussed. Furthermore, Fermi softness is investigated to evaluate the reactivity of the Fe/GN substrates surface. It is found that NO is strongly adsorbed on Fe/GN with considerable adsorption energy of 2.04-2.41 eV, while CO is relatively weaker adsorbed on the same substrates with adsorption energy of 1.10-1.53 eV. Based on our calculation, when CO and NO exist simultaneously, the possibility of adsorption CO can be neglected on the Fe/GN surface. In addition, Fermi softness is a good descriptor to characterize the reactivity of our Fe/GN surface. Our results could provide crucial information for adsorption sensing of NO on Fe/GN, which may be a useful clue for the design and fabrication of Fe-decorated graphene as NO sensors and adsorbent.