The truncated hemoglobins from Synechocystis sp. PCC 6803 and Synechococcus sp. PCC 7002 ligate the heme iron with two axial histidines (HisF8 and HisE10). In addition, these two proteins are able to form a heme-protein cross-link between a vinyl substituent and a histidine at position 16 of the H helix. The product is a protein with improved resistance to thermal and acid denaturation.