The hypomethylating agent 5-aza-2'-deoxycytidine (5-aza-CdR) and its derivatives have been successfully used for the treatment of myelodysplastic syndromes, and they frequently improve the anemia that usually accompanies these disorders. However, the molecular mechanisms underlying this action remain poorly understood. In this study, we used two erythroid models, murine erythroid leukemia cells and erythroid burst-forming unit-derived erythroblasts, to show that 5-aza-CdR induced erythroid differentiation and increased the expression of transferrin receptor 1 (TfR1) and ferrochelatase (Fech), thereby increasing iron uptake and heme biosynthesis. We have identified new regulatory E-boxes that lie outside of CpG islands in the TfR1 and Fech promoters, and the methylation status of these sites can be altered by 5-aza-CdR treatment. This in turn altered the binding of the transcription factor c-Myc to these promoter elements. Furthermore, 5-aza-CdR promoted the nuclear translocation of c-Myc and its binding to Max to form functional complexes. The coordinated actions of 5-aza-CdR on the methylation status of the target genes and in stimulating the nuclear translocation of c-Myc provide new molecular insights into the regulation of E-boxes and explain, at least in part, the increased erythroid response to 5-aza-CdR treatment.