Long-term, immunosuppression-free allograft survival has been induced in human and nonhuman primate (NHP) kidney recipients after nonmyeloablative conditioning and donor bone marrow transplantation (DBMT), resulting in transient mixed hematopoietic chimerism. However, the same strategy has consistently failed in NHP heart transplant recipients. Here, we investigated whether long-term heart allograft survival could be achieved by cotransplanting kidneys from the same donor. Cynomolgus monkeys were transplanted with heart allografts alone or heart and kidney allografts from the same major histocompatibility complex (MHC)-mismatched donors. All animals except one received DBMT, either at the same time or after a 2- to 4-month delay, plus short-term costimulation blockade and calcineurin inhibitor treatment. Long-term, immunosuppression-free heart allograft survival was consistently achieved in heart/kidney, but not heart-alone, recipients. This was not associated with greater donor/recipient histocompatibility or altered lymphoid cell reconstitution after conditioning. The maintenance of tolerance after heart/kidney transplantation was associated with the presence of forkhead box P3 (Foxp3+) regulatory T cell (Treg)-rich organized lymphoid structures in kidneys but not hearts. Substituting high-dose erythropoietin treatment for kidney transplantation was unsuccessful, suggesting that it was not the sole mechanism of action. RNA sequencing analysis revealed that gene expression in hearts from tolerant recipients closely resembled that in hearts from chronically immunosuppressed recipients but differed markedly from rejecting allografts and naïve hearts. A version of this protocol may be able to induce tolerance in patients with end-stage heart and kidney failure who require combined heart and kidney transplantation.