Lenalidomide and azacitidine are active in MDS patients, and may complement each other by targeting the bone marrow microenvironment and the malignant clone. A recent Phase I trial testing the lenalidomide and azacitidine combination yielded encouraging results; however, lenalidomide’s contribution was unclear. In this study, 18 higher-risk MDS patients were treated with the combination for seven cycles, after which lenalidomide was discontinued in eight patients who achieved a complete response, with azacitidine monotherapy continuing until disease progression. We report on three patients who relapsed on monotherapy with excess blasts at 12, 19, and 24 months, in whom lenalidomide was then resumed in combination with azacitidine. Each patient, one with normal cytogenetics at relapse; one with a 18 abnormality; and one with del(4q25), recaptured a complete response that was sustained for 5, 7, and 7+ months. We conclude that the addition of lenalidomide to azacitidine provides additional clinical benefit over azacitidine monotherapy.