The induction of tolerance towards allogeneic solid organ grafts is one of the major goals in transplantation medicine. Mesenchymal stem cells (MSC) inhibit the immune response in vitro, and thus are promising candidate cells to promote acceptance of transplanted organs in vivo. Such novel approaches of tolerance induction are needed since, to date, graft acceptance can only be maintained through life-long treatment with unspecific immunosuppressants that are associated with toxic injury, opportunistic infections and malignancies. We demonstrate that donor-derived MSC induce long-term allograft acceptance in a rat heart transplantation model, when concurrently applied with a short course of low-dose mycophenolate. This tolerogenic effect of MSC is at least partially mediated by the expression of indoleamine 2,3-dioxygenase (IDO), demonstrated by the fact that blocking of IDO with 1-methyl tryptophan (1-MT) abrogates graft acceptance. Moreover we hypothesize that MSC interact with dendritic cells (DC) in vivo, because allogeneic MSC are rejected in the long-term but DC acquire a tolerogenic phenotype after applying MSC. In summary, we demonstrate that MSC constitute a promising tool for induction of non-responsiveness in solid organ transplantation that warrants further investigation in clinical trials.