The Saccharomyces cerevisiae Ccr4-Not complex is a global regulator of transcription that is thought to regulate TATA binding protein (TBP) function at certain promoters specifically. In this paper, we show interactions between the essential domain of Not1p, which interacts with Not4p and Not5p, and the N-terminal domain of yTAF1. We isolated a temperature-sensitive nonsense allele of TAF1, taf1-4, which is synthetically lethal at the permissive temperature when combined with not4 and not5 mutants and which produces high levels of a C-terminally truncated yTAF1 derivative. Overexpression of C-terminally truncated yTAF1 is toxic in not4 or not5 mutants, whereas overexpression of full-length yTAF1 suppresses not4. Furthermore, mutations in the autoinhibitory N-terminal TAND domain of yTAF1 suppress not5, and the overexpression of similar mutants does not suppress not4. We find that, like Not5p, yTAF1 acts as a repressor of stress response element-dependent transcription. Finally, we have evidence for stress-regulated occupancy of promoter DNA by Not5p and for Not5p-dependent regulation of yTAF1 association with promoter DNA. Taken together with our finding that Not1p copurifies with glutathione S-transferase-yTaf1 in large complexes, these results provide the first molecular evidence that the Ccr4-Not complex might interact with yTAF1 to regulate its association at promoters, a function that might in turn regulate the autoinhibitory N-terminal domain of yTAF1.