Transplantation is a cure for end-stage organ failure but, in the absence of pharmacological immunosuppression, allogeneic organs are acutely rejected. Such rejection invariably results in allosensitization and accelerated rejection of secondary donor-matched grafts. Transplantation tolerance can be induced in animals and a subset of humans, and enables long-term acceptance of allografts without maintenance immunosuppression. However, graft rejection can occur long after a state of transplantation tolerance has been acquired. When such an allograft is rejected, it has been assumed that the same rules of allosensitization apply as to non-tolerant hosts and that immunological tolerance is permanently lost. Using a mouse model of cardiac transplantation, we show that when Listeria monocytogenes infection precipitates acute rejection, thus abrogating transplantation tolerance, the donor-specific tolerant state re-emerges, allowing spontaneous acceptance of a donor-matched second transplant. These data demonstrate a setting in which the memory of allograft tolerance dominates over the memory of transplant rejection.