RNA Pol II elongation in eukaryotes is coupled with a series of histone modifications. Elongating RNA Pol II can be strongly stalled by lesions on the DNA template. However, it is unclear whether RNA Pol II stalling affects elongation-associated histone modifications. We have explored this important question by investigating the function of histone H2B mono-ubiquitylation (H2Bub), a well-characterized epigenetic mark associated with RNA Pol II elongation, in the cellular response to DNA lesions induced by ultraviolet (UV) radiation. We found that, in contrast to transcription elongation, RNA Pol II stalling induced by UV lesions triggers rapid and significant H2B deubiquitylation that removes ubiquitin from H2B. Interestingly, in yeast mutant cells that lack H2B deubiquitylation enzymes, rescue of the stalled RNA Pol II by transcription-coupled repair (TCR) is significantly impaired. Thus, our study has established a direct connection between RNA Pol II stalling and a histone modification response.