Eukaryotic organisms adapt to environmental fluctuations by altering their epigenomic landscapes and transcriptional programs. Nucleosomal histones carry vital epigenetic information and regulate gene expression, yet the mechanisms underlying chromatin-bound histone exchange remain elusive. Here, we found that histone H2Bs are globally degraded in Caenorhabditis elegans during starvation. Our genetic screens identified mutations in ubiquitin and ubiquitin-related enzymes that block H2B degradation in starved animals, identifying lysine 31 as the crucial residue for chromatin-bound H2B ubiquitination and elimination. Retention of aberrant nucleosomal H2B increased the association of the FOXO transcription factor DAF-16 with chromatin, generating an ectopic gene expression profile detrimental to animal viability when insulin/IGF signaling was reduced in well-fed animals. Furthermore, we show that the ubiquitin-proteasome system regulates chromosomal histone turnover in human cells. During larval development, C. elegans epidermal cells undergo H2B turnover after fusing with the epithelial syncytium. Thus, histone degradation may be a widespread mechanism governing dynamic changes of the epigenome.