Background: Disease relapse after allogeneic stem cell transplantation (allo-SCT) is the main challenge for curing acute myeloid leukemia (AML) and myelodysplastic syndrome (MDS). We investigated the overall survival (OS) after allo-SCT relapse according to different therapeutic approaches. Methods: We analyzed 134 patients who relapsed after allo-SCT performed between 2015 and 2021 at Saint-Antoine University Hospital, Paris and Spedali Civili di Brescia, Brescia. Of these, 103 (77%) were treated, comprising 69/103 (67%) who received therapy in overt relapse and 34/103 (33%) who were treated in a pre-emptive manner when molecular/cytogenetics recurrence or mixed chimerism occurred. The treatment was donor lymphocyte infusion (DLI)-based for 40/103 (39%) patients. Results: The 1-, 2-, and 5-year OS of patients treated with DLI (n = 40) was 67%, 34%, and 34%, respectively, for those treated preventively (n = 20) and 43%, 20%, and 20%, respectively, for those treated in overt relapse (n = 20) (p < 0.01). The 1-, 2-, and 5-year OS of patients treated without DLI (n = 63) was 54%, 40%, and 26%, respectively, for those treated preventively (n = 14) and 17%, 5%, and 0%, respectively, for those treated in overt relapse (n = 49) (p < 0.01). Conclusions: Relapse treatment with a pre-emptive strategy was associated with improved outcomes, particularly when DLI was employed.