The binding of O2 and NO to heme in heme-nitric oxide/oxygen-binding (H-NOX) proteins has been investigated with DFT as well as dispersion-corrected DFT methods. The local protein environment was accounted for by including the six nearest surrounding residues in the studied systems. Attention was also paid to the effects of the protein environment, particularly the distal Tyr140, on the proximal iron-histidine (Fe-His) binding. The Heme-AB (AB = O2, NO) and Fe-His binding energies in iron porphyrin FeP(His)(AB), myoglobin Mb(AB), H-NOX(AB), and Tyr140 → Phe mutated H-NOX[Y140F(AB)] were determined for comparison. The calculated stabilization of bound O2 is even higher in H-NOX than that in a myoglobin (Mb), consistent with the observation that the H-NOX domain of T. tengcongensis has a very high affinity for its oxygen molecule. Among the two different X-ray crystal structures for the Tt H-NOX protein, the calculated results for both AB = O2 and NO appear to support the crystal structure with the PDB code 1XBN , where the Trp9 and Asn74 residues do not form a hydrogen-bonding network with Tyr140. A hydrogen bond interaction from the polar residue does not have obvious effects on the Fe-His binding strength, but a dispersion contribution to Ebind(Fe-His) may be significant, depending on the crystal structure used. We speculate that the Fe-His binding strength in the deoxy form of a native protein could be an important factor in determining whether the bond of His to Fe is broken or maintained upon binding of NO to Fe.