The Ccr4-Not complex is a multifunctional regulatory platform composed of nine subunits that controls diverse cellular events including mRNA degradation, protein ubiquitination, and transcription. In this study, we identified the yeast Saccharomyces cerevisiae osmotic and oxidative stress transcription factor Skn7 as a new target for regulation by the Ccr4-Not complex. Skn7 interacts with Not1 in a two-hybrid assay and coimmunoprecipitates with Not5 in a Not4-dependent manner. Skn7-dependent expression of OCH1 and Skn7 binding to the OCH1 promoter are increased in not4Delta or not5Delta mutants. Skn7 purified from wild-type cells but not from not4Delta cells is associated with the Srb10 kinase. This kinase plays a central role in the regulation of Skn7 by Not4, since increased OCH1 expression in not4Delta cells requires Srb10. These results reveal a critical role for the Ccr4-Not complex in the mechanism of activation of Skn7 that is dependent upon the Srb10 kinase.