Non-degradative histone ubiquitylation plays a myriad of well-defined roles in the regulation of gene expression and choreographing DNA damage repair pathways. In contrast, the contributions of degradative histone ubiquitylation on genomic processes has remained elusive. Recently, the APC/C has been shown to ubiquitylate histones to regulate gene expression in pluripotent cells, but the molecular mechanism is unclear. Here we show that despite directly binding to the nucleosome through subunit APC3, the APC/C is unable to ubiquitylate nucleosomal histones. In contrast, extranucleosomal H2A/H2B and H3/H4 complexes are broadly ubiquitylated by the APC/C in an unexpected manner. Using a combination of cryo-electron microscopy (cryo-EM) and biophysical and enzymatic assays, we demonstrate that APC8 and histone tails direct APC/C-mediated polyubiquitylation of core histones in the absence of traditional APC/C substrate degron sequences. Taken together, our work implicates APC/C-nucleosome tethering in the degradation of diverse chromatin-associated proteins and extranucleosomal histones for the regulation of transcription and the cell cycle and for preventing toxicity due to excess histone levels.