Post-translational histone modifications have important regulatory roles in chromatin structure and function. One example of such modifications is histone ubiquitination, which occurs predominately on histone H2A and H2B. Although the recent identification of the ubiquitin ligase for histone H2A has revealed important roles for H2A ubiquitination in Hox gene silencing as well as in X-chromosome inactivation, the enzyme(s) involved in H2A deubiquitination and the function of H2A deubiquitination are not known. Here we report the identification and functional characterization of the major deubiquitinase for histone H2A, Ubp-M (also called USP16). Ubp-M prefers nucleosomal substrates in vitro, and specifically deubiquitinates histone H2A but not H2B in vitro and in vivo. Notably, knockdown of Ubp-M in HeLa cells results in slow cell growth rates owing to defects in the mitotic phase of the cell cycle. Further studies reveal that H2A deubiquitination by Ubp-M is a prerequisite for subsequent phosphorylation of Ser 10 of H3 and chromosome segregation when cells enter mitosis. Furthermore, we demonstrate that Ubp-M regulates Hox gene expression through H2A deubiquitination and that blocking the function of Ubp-M results in defective posterior development in Xenopus laevis. This study identifies the major deubiquitinase for histone H2A and demonstrates that H2A deubiquitination is critically involved in cell cycle progression and gene expression.