The inherent immunosuppressive properties and low immunogenicity of mesenchymal stems cells (MSCs) suggested their therapeutic potential in transplantation. We investigated whether MSCs could prolong allograft survival. Treatment involving infusion of MSCs into BALB/c recipients 24 hours after receiving a heart allograft from a C57BL/6 donor significantly abated rejection and doubled graft mean survival time compared to untreated recipients. Furthermore, combination therapy of MSCs and low-dose Rapamycin (Rapa) achieved long-term heart graft survival (>100 days) with normal histology. The treated recipients readily accepted donor skin grafts but rejected third-party skin grafts, indicating the establishment of tolerance. Tolerant recipients exhibited neither intragraft nor circulating antidonor antibodies, but demonstrated significantly high frequencies of both tolerogenic dendritic cells (Tol-DCs) and CD4(+)CD25(+)Foxp3(+)T cells in the spleens. Infusion of GFP(+)C57BL/6-MSCs in combination with Rapa revealed that the GFP-MSCs accumulated in the lymphoid organs and grafts of tolerant recipients. Thus, engraftment of infused MSCs within the recipient's lymphoid organs and allograft appeared to be instrumental in the induction of allograft-specific tolerance when administered in combination with a subtherapeutic dose of Rapamycin. This study supports the clinical applicability of MSCs in transplantation.