The PHD domain is found in many chromatin-associated proteins and functions to recruit effector proteins to chromatin through its ability to bind both methylated and unmethylated histone residues. Here, we show that the dual PHD domains of Rco1 – a member of the Rpd3S histone deacetylase complex recruited to transcribing genes – operate in a combinatorial manner in targeting the Rpd3S complex to histone H3 in chromatin. While mutations in either the first or second PHD domain allow for Rpd3S complex formation, the assembled complexes from these mutants cannot recognize nucleosomes or function to maintain chromatin structure and prevent cryptic transcriptional initiation from within transcribed regions. Taken together, our findings establish a critical role of combinatorial readout in maintaining chromatin organization and in enforcing the transcriptional fidelity of genes.