TAL1 is a critical transcription factor required for hematopoiesis. However, perturbation of its activity often leads to T cell leukemia. Whether and how its transcriptional activities are regulated during hematopoiesis remains to be addressed. Here, we show that TAL1 is associated with histone demethylase complexes containing lysine-specific demethylase 1 (LSD1), RE1 silencing transcription factor corepressor (CoREST), histone deacetylase 1 (HDAC1), and histone deacetylase 2 in erythroleukemia and T cell leukemia cells. The enzymatic domain of LSD1 plays an important role in repressing the TAL1-directed transcription of GAL4 reporter linked to a thymidine kniase minimal promoter. Furthermore, we demonstrate that the TAL1-associated LSD1, HDAC1, and their enzymatic activities are coordinately down-regulated during the early phases of erythroid differentiation. Consistent with the rapid changes of TAL1-corepressor complex during differentiation, TAL1 recruits LSD1 to the silenced p4.2 promoter in undifferentiated, but not in differentiated, murine erythroleukemia (MEL) cells. Finally, shRNA-mediated knockdown of LSD1 in MEL cells resulted in derepression of the TAL1 target gene accompanied by increasing dimeH3K4 at the promoter region. Thus, our data revealed that histone lysine demethylase LSD1 may negatively regulate TAL1-mediated transcription and suggest that the dynamic regulation of TAL1-associated LSD1/HDAC1 complex may determine the onset of erythroid differentiation programs.