Regulated migration of hematopoietic stem cells is fundamental for hematopoiesis. The molecular mechanisms underlying stem cell trafficking are poorly defined. Based on a short hairpin RNA library and stromal cell-derived factor-1 (SDF-1) migration screening assay, we identified the histone 3 lysine 27 demethylase UTX (Kdm6a) as a novel regulator for hematopoietic cell migration. Using hematopoietic stem and progenitor cells from our conditional UTX knockout (KO) mice, we were able to confirm the regulatory function of UTX on cell migration. Moreover, adult female conditional UTX KO mice displayed myelodysplasia and splenic erythropoiesis, whereas UTX KO males showed no phenotype. During development, all UTX KO female and a portion of UTX KO male embryos developed a cardiac defect, cranioschisis, and died in utero. Therefore, UTY, the male homolog of UTX, can compensate for UTX in adults and partially during development. Additionally, we found that UTX knockdown in zebrafish significantly impairs SDF-1/CXCR4-dependent migration of primordial germ cells. Our data suggest that UTX is a critical regulator for stem cell migration and hematopoiesis.