Heme oxygenase (HO) is a mono-oxygenase utilizing heme and molecular oxygen (O2) as substrates to generate biliverdin-IXα and carbon monoxide (CO). HO-1 is inducible under stress conditions, while HO-2 is constitutive. A balance between heme and CO was shown to regulate cell death and survival in many experimental models. However, direct molecular targets to which CO binds to regulate cellular functions remained to be fully examined. We have revealed novel roles of CO-responsive proteins, cystathionine β-synthase (CBS) and progesterone receptor membrane component 1 (PGRMC1), in regulating cellular functions. CBS possesses a prosthetic heme that allows CO binding to inhibit the enzyme activity and to regulate H2S generation and/or protein arginine methylation. On the other hand, in response to heme accumulation in cells, PGRMC1 forms a stable dimer through stacking interactions of two protruding heme molecules. Heme-mediated PGRMC1 dimerization is necessary to interact with EGF receptor and cytochromes P450 that determine cell proliferation and xenobiotic metabolism. Furthermore, CO interferes with PGRMC1 dimerization by dissociating the heme stacking, and thus results in modulation of cell responses. This article reviews the intriguing functions of these two proteins in response to inducible and constitutive levels of CO with their pathophysiological implications.