Histone modifications are major epigenetic factors regulating gene expression. They play important roles in maintaining stem cell pluripotency and in cancer pathogenesis. Different modifications may combine to form complex "histone codes." Recent high-throughput technologies, such as "ChIP-chip" and "ChIP-seq," have generated high-resolution maps for many histone modifications on the human genome. Here we use these maps to build a Bayesian network to infer causal and combinatorial relationships among histone modifications and gene expression. A pilot network derived by the same method among polycomb group (PcG) genes and H3K27 trimethylation is accurately supported by current literature. Our unbiased network model among histone modifications is also well supported by cross-validation results. It not only confirmed already known relationships, such as those of H3K27me3 to gene silencing, H3K4me3 to gene activation and the effect of bivalent modification of both H3K4me3 and H3K27me3, but also identified many other relationships that may predict new epigenetic interactions important in epigenetic gene regulation. Our automated inference method, which is potentially applicable to other ChIP-chip or ChIP-seq data analyses, provides a much-needed guide to deciphering the complex histone codes.