Gene expression in higher organisms is thought to be regulated by a complex network of transcription factor binding and chromatin modifications, yet the relative importance of these two factors remains a matter of debate. Here, we show that a computational approach allows surprisingly accurate prediction of histone modifications solely from knowledge of transcription factor binding both at promoters and at potential distal regulatory elements. This accuracy significantly and substantially exceeds what could be achieved by using DNA sequence as an input feature. Remarkably, we show that transcription factor binding enables strikingly accurate predictions across different cell lines. Analysis of the relative importance of specific transcription factors as predictors of specific histone marks recapitulated known interactions between transcription factors and histone modifiers. Our results demonstrate that reported associations between histone marks and gene expression may be indirect effects caused by interactions between transcription factors and histone-modifying complexes.