To ensure cell survival and growth during temperature increase, eukaryotic organisms respond with transcriptional activation that results in accumulation of proteins that protect against damage and facilitate recovery. To define the global cellular adaptation response to heat stress, we performed a systematic genetic screen that yielded 277 yeast genes required for growth at high temperature. Of these, the Rpd3 histone deacetylase complex was enriched. Global gene expression analysis showed that Rpd3 partially regulated gene expression upon heat shock. The Hsf1 and Msn2/4 transcription factors are the main regulators of gene activation in response to heat stress. RPD3-deficient cells had impaired activation of Msn2/4-dependent genes, while activation of genes controlled by Hsf1 was deacetylase-independent. Rpd3 bound to heat stress-dependent promoters through the Msn2/4 transcription factors, allowing entry of RNA Pol II and activation of transcription upon stress. Finally, we found that the large, but not the small Rpd3 complex regulated cell adaptation in response to heat stress.