Mesenchymal stem cells (MSCs) display immunomodulatory properties mediated by various factors, including inducible nitric oxide synthase (iNOS). Since heme oxygenase-1 (HO-1) is a potent immunosuppressive enzyme, we tested the hypothesis that HO-1 could mediate the immunosuppressive effects of MSCs. We generated adult rat MSCs that inhibited T-cell proliferation in vitro. These MSCs expressed both HO-1 and iNOS. In vitro, whereas neither HO-1 nor iNOS inhibition alone could interfere with the immunosuppressive properties of rat MSCs, simultaneous inhibition of both enzymes restored T-cell proliferation. In vivo, injection of MSCs significantly delayed heart allograft rejection, and inhibition of either HO-1 or iNOS totally reversed the protective activity of MSCs, inducing rejection. Adult human MSCs also expressed HO-1; in these cells, HO-1 inhibition was sufficient to completely block their immunosuppressive capacity. In conclusion, we show, for the first time, that HO-1 mediates the immunosuppressive properties of rat and human MSCs.