Large-scale chromatin immunoprecipitation (ChIP) studies have been effective in unravelling the distribution of DNA-binding transcription factors along eukaryotic genomes, but specificity determinants remain elusive. Gene-regulatory regions display distinct histone variants and modifications (or marks). An attractive hypothesis is that these marks modulate protein recognition, but whether or not this applies to transcription factors remains unknown. Based on large-scale datasets and quantitative ChIP, we dissect the correlations between 35 histone marks and genomic binding by the transcription factor Myc. Our data reveal a relatively simple combinatorial organization of histone marks in human cells, with a few main groups of marks clustering on distinct promoter populations. A stretch of chromatin bearing high H3 K4/K79 methylation and H3 acetylation (or 'euchromatic island'), which is generally associated with a pre-engaged basal transcription machinery, is a strict pre-requisite for recognition of any target site by Myc (whether the consensus CACGTG or an alternative sequence). These data imply that tethering of a transcription factor to restricted chromatin domains is rate-limiting for sequence-specific DNA binding in vivo.