H-NOX proteins are mutated to exhibit improved or optimal kinetic and thermodynamic properties for blood gas NO delivery. The engineered H-NOX proteins comprise mutations that impart altered NO or O2 ligand-binding relative to the corresponding wild-type H-NOX domain, and are operative as physiologically compatible mammalian blood NO gas carriers. The invention also provides pharmaceutical compositions, kits, and methods that use wild-type or mutant H-NOX proteins for the treatment of any condition for which delivery of NO is beneficial.