The response to stressful stimuli requires rapid, precise, and dynamic gene expression changes that must be coordinated across the genome. To gain insight into the temporal ordering of genome reorganization, we investigated dynamic relationships between changing nucleosome occupancy, transcription factor binding, and gene expression in Saccharomyces cerevisiae yeast responding to oxidative stress. We applied deep sequencing to nucleosomal DNA at six time points before and after hydrogen peroxide treatment and revealed many distinct dynamic patterns of nucleosome gain and loss. The timing of nucleosome repositioning was not predictive of the dynamics of downstream gene expression change but instead was linked to nucleosome position relative to transcription start sites and specific cis-regulatory elements. We measured genome-wide binding of the stress-activated transcription factor Msn2p over time and found that Msn2p binds different loci with different dynamics. Nucleosome eviction from Msn2p binding sites was common across the genome; however, we show that, contrary to expectation, nucleosome loss occurred after Msn2p binding and in fact required Msn2p. This negates the prevailing model that nucleosomes obscuring Msn2p sites regulate DNA access and must be lost before Msn2p can bind DNA. Together, these results highlight the complexities of stress-dependent chromatin changes and their effects on gene expression.