Tolerance induction by means of costimulation blockade has been successfully applied in solid organ transplantation; however, its efficacy in vascularized composite allotransplantation, containing a vascularized bone marrow component and thus a constant source of donor-derived stem cells, remains poorly explored. In this study, osteomyocutaneous allografts (alloOMCs) from Balb/c (H2d) mice were transplanted into C57BL/6 (H2b) recipients. Immunosuppression consisted of 1 mg anti-CD154 on day 0, 0.5 mg CTLA4Ig on day 2 and rapamycin (RPM; 3 mg/kg per day from days 0–7, then every other day for 3 weeks). Long-term allograft survival, donor-specific tolerance and donor–recipient cell trafficking were evaluated. Treatment with costimulation blockade plus RPM resulted in long-term graft survival (>120 days) of alloOMC in 12 of 15 recipients compared with untreated controls (median survival time [MST] ≈10.2 ± 0.8 days), RPM alone (MST ≈33 ± 5.5 days) and costimulation blockade alone (MST ≈45.8 ± 7.1 days). Donor-specific hyporesponsiveness in recipients with viable grafts was demonstratedin vitro. Evidence of donor-specific tolerance was further assessedin vivoby secondary donor-specific skin graft survival and third-party graft rejection. A significant increase of Foxp3+ regulatory T cells was evident in tolerant animals. Donor cells populated peripheral blood, thymus, and both donor and recipient bone marrow. Consequently, combined anti-CD154/CTLA4Ig costimulation blockade-based therapy induces donor-specific tolerance in a stringent murine alloOMC transplant model.