Soluble guanylate cyclase (sGC) is a heme-containing enzyme that catalyzes cGMP production upon sensing NO. While the CO adduct, sGC-CO, is much less active, the allosteric regulator BAY 41-2272 stimulates the cGMP productivity to the same extent as that of sGC-NO. The stimulatory effect has been thought to be likely associated with Fe-His bond cleavage leading to 5-coordinate CO-heme, but the detailed mechanism remains unresolved. In this study, we examined the mechanism under the condition including BAY 41-2272, 2'-deoxy-3'-GMP and foscarnet. The addition of these effectors caused the original 6-coordinate CO-heme to convert to an end product that was an equimolar mixture of a 5- and a new 6-coordinate CO-heme, as assessed by IR spectral measurements. The two types of CO-hemes in the end product were further confirmed by CO dissociation kinetics. Stopped-flow measurements under the condition indicated that the ferrous sGC bound CO as two reversible steps, where the primary step was assigned to the full conversion of the ferrous enzyme to the 6-coordinate CO-heme, and subsequently followed by the slower second step leading a partial conversion of the 6-coordinate CO-heme to the 5-coordinate CO-heme. The observed rates for both steps linearly depended on CO concentrations. The unexpected CO dependence of the rates in the second step supports a multistep mechanism, in which the 5-coordinate CO-heme is led by CO release from a putative bis-carbonyl intermediate that is likely provided by the binding of a second CO to the 6-coordinate CO-heme. This mechanism provides a new aspect on the activation of sGC by CO.