Histone lysine methylation and demethylation are considered critical steps in transcriptional regulation. In this report, we performed chromatin immunoprecipitation with microarray technology (ChIP-chip) analysis to examine the genome-wide occupancy of H3K9-me2 during all-trans-retinoic acid (ATRA)-induced differentiation of HL-60 promyelocytic leukemia cells. Using this approach, we found that KDM3B, which contains a JmjC domain, was downregulated during differentiation through the recruitment of a corepressor complex. Furthermore, KDM3B displayed histone H3K9-me1/2 demethylase activity and induced leukemogenic oncogene lmo2 expression via a synergistic interaction with CBP. Here, we found that KDM3B repressed leukemia cell differentiation and was upregulated in blood cells from acute lymphoblastic leukemia (ALL)-type leukemia patients. The combined results of this study provide evidence that the H3K9-me1/2 demethylase KDM3B might play a role in leukemogenesis via activation of lmo2 through interdependent actions with the histone acetyltransferase (HAT) complex containing CBP.