Post-translational modifications of the histone protein components of eukaryotic chromatin play an important role in the regulation of chromatin structure and gene expression (1). Given the requirement of Rad6/Bre1-dependent ubiquitination of histone H2B for H3 dimethylation (at lysines 4 and 79) and gene silencing (2-7), removal of ubiquitin from H2B may have a significant regulatory effect on transcription. Here we show that a putative deubiquitinating enzyme, Ubp8, is a structurally nonessential component of both the Spt-Ada-Gcn5-acetyltransferase (SAGA) and SAGA-like (SLIK) histone acetyltransferase (HAT) complexes in yeast. Disruption of this gene dramatically increases the cellular level of ubiquitinated-H2B, and SAGA and SLIK are shown to have H2B deubiquitinase activity. These findings demonstrate, for the first time, how the ubiquitin moiety can be removed from histone H2B in a regulated fashion. Ubp8 is required for full expression of the SAGA- and SLIK-dependent gene GAL10 and is recruited to the upstream activation sequence (UAS) of this gene under activating conditions, while Rad6 dissociates. Furthermore, trimethylation of H3 at lysine 4 within the UAS increases significantly under activating conditions, and remarkably, Ubp8 is shown to have a role in regulating the methylation status of this residue. Collectively, these data suggest that the SAGA and SLIK HAT complexes can regulate an integrated set of multiple histone modifications, counteracting repressive effects that alter chromatin and regulate gene expression.