Covalent histone modifications are highly conserved and play multiple roles in eukaryotic transcription regulation. Here, we mapped 26 histone modifications genome-wide in exponentially growing yeast and during a dramatic transcriptional reprogramming-the response to diamide stress. We extend prior studies showing that steady-state histone modification patterns reflect genomic processes, especially transcription, and display limited combinatorial complexity. Interestingly, during the stress response we document a modest increase in the combinatorial complexity of histone modification space, resulting from roughly 3% of all nucleosomes transiently populating rare histone modification states. Most of these rare histone states result from differences in the kinetics of histone modification that transiently uncouple highly correlated marks, with slow histone methylation changes often lagging behind the more rapid acetylation changes. Explicit analysis of modification dynamics uncovers ordered sequences of events in gene activation and repression. Together, our results provide a comprehensive view of chromatin dynamics during a massive transcriptional upheaval.