Recurrent somatic loss-of-function mutations in histone demethylases are frequently detected in cancer. However, whether loss of a histone demethylase can cause cancer has not been determined. Here, we report that knockout of the histone demethylase Utx in mice causes a chronic myelomonocytic leukemia (CMML)-like disease with splenomegaly, monocytosis, and extramedullary hematopoiesis. Mutational analysis of patient data indicated that UTX mutations occur simultaneously with TP53 mutations in myeloid malignancies, and combined inactivation of Utx and Trp53 accelerated the development of CMML in a cell-autonomous manner. Utx loss caused increased self-renewal of hematopoietic stem cells and predisposed hematopoietic stem cells to differentiate into myeloid-derived lineages. Transcriptome and chromatin immunoprecipitation analyses revealed that Utx activates key transcriptional factors required for erythroid differentiation by modulating histone H3 lysine 27 and lysine 4 trimethylation. Our results suggest that Utx suppresses CMML formation by controlling hematopoietic stem cell self-renewal and differentiation.