Bmi-1 and SALL4 are putative oncogenes that modulate stem cell pluripotency and play a role in leukemogenesis. Murine Sall4 also has been shown to play an essential role in maintaining the properties of ES cells and governing the fate of the primitive inner cell mass. Here, we demonstrate that transcription from the Bmi-1 promoter is strikingly activated by SALL4 in a dose-dependent manner by using a luciferase reporter gene assay. Both promoter deletion construct studies and ChIP from a myeloid stem cell line, 32D, demonstrate that SALL4 binds to a specific region of the Bmi-1 promoter. Deletion of one copy of Sall4 by gene targeting in mouse bone marrow significantly reduced Bmi-1 expression. Reducing SALL4 expression by siRNA in the HL-60 leukemia cell line also results in significant down-regulation of Bmi-1. Furthermore, Bmi-1 expression is up-regulated in transgenic mice that constitutively overexpress human SALL4, and the levels of Bmi-1 in these mice increase as they progress from normal to preleukemic (myelodysplastic syndrome) and leukemic (acute myeloid leukemia) stages. High levels of H3–K4 trimethylation and H3–K79 dimethylation were observed in the SALL4 binding region of the Bmi-1 promoter. These findings suggest a novel link between SALL4 and Bmi-1 in regulating self-renewal of normal and leukemic stem cells. An increase in histone H3–K4 and H3–K79 methylation within the Bmi-1 promoter provides an epigenetic mechanism for histone modifications in SALL4-mediated Bmi-1 gene deregulation.