Cks1, Cdk1 (Cdc28), and the proteasome are required for efficient transcriptional induction of GAL1 and other genes in Saccharomyces cerevisiae. We show here that one function of these proteins is to reduce nucleosome density on chromatin in a gene induction-specific manner. The transcriptional requirement for Cks1 can be bypassed if nucleosome density is reduced by an alternative pathway, indicating that this is the primary function of Cks1 in the context of gene induction. We further show that Cks1, Cdk1, and the 19S subunit of the proteasome are recruited to chromatin by binding directly to the histone H4 amino-terminal tail. However, this activity of the proteasome does not require the protease activity associated with the 20S subunit. These data suggest a model where binding of a complex consisting of Cks1, Cdk1, and the 19S proteasome to histone H4 leads to removal of nucleosomes via a nonproteolytic activity of the proteasome.