Biochemical experiments indicate that transcriptional elongation by RNA polymerase II (Pol II) is inhibited by nucleosomes and hence requires chromatin-modifying activities. Here, we examine the fate of histones upon passage of elongating Pol II in vivo. Histone density throughout the entire Saccharomyces cerevisiae GAL10 coding region is inversely correlated with Pol II association and transcriptional activity, suggesting that the elongating Pol II machinery efficiently evicts core histones from the DNA. Furthermore, new histones appear to be deposited onto DNA less than 1 min after passage of Pol II. Transcription-dependent deposition of histones requires the FACT complex that travels with elongating Pol II. Our results suggest that Pol II transcription generates a highly dynamic equilibrium of histone eviction and histone deposition and that there is significant histone exchange throughout most of the yeast genome within a single cell cycle.