Histones are essential proteins that package the DNA in all eukaryotes into chromosomes. However, histones can accumulate upon a decrease in DNA synthesis that occurs at the end of S-phase or following replication arrest. These positively charged histones can associate non-specifically with the negatively charged DNA and other cellular biomolecules, impairing their normal function. Hence, cells have evolved numerous strategies to limit the generation of excess histones and prevent deleterious effects due to their accumulation. Such strategies for histone regulation are discussed here, with particular emphasis on recent studies that implicate the DNA damage checkpoint kinases in the regulation of histone levels, especially in response to replication inhibition. We have also focused upon the recently discovered regulatory mechanism involving histone proteolysis in the budding yeast. Additionally, we speculate that cells may possess a surveillance mechanism for sensing histone levels, particularly in the G1 and S-phases of the cell cycle. Proper regulation of histone levels has major implications for the maintenance of epigenetic marks on chromatin, genomic stability and the packaging of sperm DNA.