Cells have the ability to sense, respond and adapt to environmental fluctuations. Stress causes a massive reorganization of the transcriptional program. Many examples of histone post-translational modifications (PTMs) have been associated with transcriptional activation or repression under steady-state growth conditions. Comparatively less is known about the role of histone PTMs in the cellular adaptive response to stress. Here, we performed high-throughput genetic screenings that provide a novel global map of the histone residues required for transcriptional reprogramming in response to heat and osmotic stress. Of note, we observed that the histone residues needed depend on the type of gene and/or stress, thereby suggesting a “personalized”, rather than general, subset of histone requirements for each chromatin context. In addition, we identified a number of new residues that unexpectedly serve to regulate transcription. As a proof of concept, we characterized the function of the histone residues H4-S47 and H4-T30 in response to osmotic and heat stress, respectively. Our results uncover novel roles for the kinases Cla4 and Ste20, yeast homologs of the mammalian PAK2 family, which phosphorylate H4-S47 and for the kinase Ste11 that targets H4-T30. This study provides new insights into the role of histone residues in transcriptional regulation under stress conditions.