Epigenetic mechanisms play important regulatory roles in hematopoiesis and hematopoietic stem cell (HSC) function. Subunits of polycomb repressive complex 1 (PRC1), the major histone H2A ubiquitin ligase, are critical for both normal and pathological hematopoiesis; however, it is unclear which of the several counteracting H2A deubiquitinases functions along with PRC1 to control H2A ubiquitination (ubH2A) level and regulates hematopoiesis in vivo. Here we investigated the function of Usp16 in mouse hematopoiesis. Conditional deletion of Usp16 in bone marrow resulted in a significant increase of global ubH2A level and lethality. Usp16 deletion did not change HSC number but was associated with a dramatic reduction of mature and progenitor cell populations, revealing a role in governing HSC lineage commitment. ChIP- and RNA-sequencing studies in HSC and progenitor cells revealed that Usp16 bound to many important hematopoietic regulators and that Usp16 deletion altered the expression of genes in transcription/chromosome organization, immune response, hematopoietic/lymphoid organ development, and myeloid/leukocyte differentiation. The altered gene expression was partly rescued by knockdown of PRC1 subunits, suggesting that Usp16 and PRC1 counterbalance each other to regulate cellular ubH2A level and gene expression in the hematopoietic system. We further discovered that knocking down Cdkn1a (p21cip1), a Usp16 target and regulated gene, rescued the altered cell cycle profile and differentiation defect of Usp16-deleted HSCs. Collectively, these studies identified Usp16 as one of the histone H2A deubiquitinases, which coordinates with the H2A ubiquitin ligase PRC1 to regulate hematopoiesis, and revealed cell cycle regulation by Usp16 as key for HSC differentiation.