Nucleosomes are essential for proper chromatin organization and the maintenance of genome integrity. Histones are post-translationally modified and often evicted at sites of DNA breaks, facilitating the recruitment of repair factors. Whether such chromatin changes are localized or genome-wide is debated. Here we show that cellular levels of histones drop 20-40% in response to DNA damage. This histone loss occurs from chromatin, is proteasome-mediated and requires both the DNA damage checkpoint and the INO80 nucleosome remodeler. We confirmed reductions in histone levels by stable isotope labeling of amino acids in cell culture (SILAC)-based mass spectrometry, genome-wide nucleosome mapping and fluorescence microscopy. Chromatin decompaction and increased fiber flexibility accompanied histone degradation, both in response to DNA damage and after artificial reduction of histone levels. As a result, recombination rates and DNA-repair focus turnover were enhanced. Thus, we propose that a generalized reduction in nucleosome occupancy is an integral part of the DNA damage response in yeast that provides mechanisms for enhanced chromatin mobility and homology search.