Abstract: The Mediator complex transmits activation signals from DNA bound transcription factors to the core transcription machinery. Genome wide localization studies have demonstrated that Mediator occupancy not only correlates with high levels of transcription, but that the complex also is present at transcriptionally silenced locations. We provide evidence that Mediator localization is guided by an interaction with histone tails, and that this interaction is regulated by their post-translational modifications. A quantitative, high-density genetic interaction map revealed links between Mediator components and factors affecting chromatin structure, especially histone deacetylases. Peptide binding assays demonstrated that pure wild-type Mediator forms stable complexes with the tails of Histone H3 and H4. These binding assays also showed Mediator-histone H4 peptide interactions are specifically inhibited by acetylation of the histone H4 lysine 16, a residue critical in transcriptional silencing. Finally, these findings were validated by tiling array analysis that revealed a broad correlation between Mediator and nucleosome occupancy in vivo, but a negative correlation between Mediator and nucleosomes acetylated at histone H4 lysine 16. Our studies show that chromatin structure and the acetylation state of histones are intimately connected to Mediator localization.