Polycomb group (PcG) proteins establish and maintain genetic programs that regulate cell-fate decisions. The Drosophila multi sex combs (mxc) gene was previously categorized as a PcG gene; however, a mechanistic connection between Polycomb and Mxc has not been elucidated. Mutations in mxc also lead to loss of tissue maintenance, which is most evident in the male and female gonad. Here we find that loss of Mxc leads to changes in the ratios of key proteins, called histones, that are important for packaging DNA and, ultimately, for regulating gene expression. Our data suggest that changes in the ratio of histone proteins leads to persistent DNA damage, which contributes to loss of stem cells and failure to maintain tissues.