Peripheral tolerance can be achieved in many but not all murine allograft models. The requirements for controlling more aggressive immune responsiveness and generating peripheral tolerance in stringent allograft models are unknown. Understanding these requirements will provide insight toward ultimately achieving tolerance in humans, which are also resistant. We now demonstrate that the combination of donor-specific transfusion, anti-CD45RB, and anti-CD154 uniformly achieves >90-d survival of BALB/c skin allografts on C57BL/6 recipients. Recipients exhibit marked hyporesponsiveness to alloantigen in vitro. In distinct contrast to less rigorous models, engraftment remains absolutely dependent on cytotoxic T lymphocyte antigen 4 signaling, even after grafts are healed, suggesting that prolonged engraftment cannot simply be attributed to more effective depletion of alloreactive T cells but is actively maintained by regulation. Concordantly, we show that both CD4 and CD8 regulatory cells are required and can transfer donor-specific tolerance to naïve recipients. Nonetheless, most recipients ultimately develop gradual graft loss (median survival time = 140 d), suggesting that alloreactive cells emerging from the thymus eventually overwhelm regulatory capacity. In agreement, adding thymectomy to the regimen results in permanent engraftment (>250 d) and donor-specific tolerance not observed previously in this model. These results highlight the potency of both CD4 and CD8 regulatory cells but also suggest that in stringent settings, regulatory T cell longevity and capacity for infectious tolerance compete with prolonged graft immunogenicity and thymic output. These results provide insight into the mechanisms of tolerance in stringent models and provide a rational basis for innovative tolerogenic strategies in humans.