Histone H2A lysine 119 (H2AK119Ub) is monoubiquitinated by Polycomb repressive complex 1 and deubiquitinated by Polycomb repressive deubiquitinase complex (PR-DUB). PR-DUB cleaves H2AK119Ub to restrict focal H2AK119Ub at Polycomb target sites and to protect active genes from aberrant silencing. The PR-DUB subunits (BAP1 and ASXL1) are among the most frequently mutated epigenetic factors in human cancers. How PR-DUB establishes specificity for H2AK119Ub over other nucleosomal ubiquitination sites and how disease-associated mutations of the enzyme affect activity are unclear. Here, we determine a cryo-EM structure of human BAP1 and the ASXL1 DEUBAD in complex with a H2AK119Ub nucleosome. Our structural, biochemical, and cellular data reveal the molecular interactions of BAP1 and ASXL1 with histones and DNA that are critical for restructuring the nucleosome and thus establishing specificity for H2AK119Ub. These results further provide a molecular explanation for how >50 mutations in BAP1 and ASXL1 found in cancer can dysregulate H2AK119Ub deubiquitination, providing insight into understanding cancer etiology.