Histone modifications contribute to gene regulation in eukaryotes. We analyzed genome-wide histone H3 Lysine (Lys) 4 trimethylation and histone H3 Lys 9 acetylation (two modifications typically associated with active genes) in meristematic cells at the base and expanded cells in the blade of the maize (Zea mays) leaf. These data were compared with transcript levels of associated genes. For individual genes, regulations (fold changes) of histone modifications and transcript levels were much better correlated than absolute intensities. When focusing on regulated histone modification sites, we identified highly regulated secondary H3 Lys 9 acetylation peaks on upstream promoters (regulated secondary upstream peaks [R-SUPs]) on 10% of all genes. R-SUPs were more often found on genes that were up-regulated toward the blade than on down-regulated genes and specifically, photosynthetic genes. Among those genes, we identified six genes encoding enzymes of the C4 cycle and a significant enrichment of genes associated with the C4 trait derived from transcriptomic studies. On the DNA level, R-SUPs are frequently associated with ethylene-responsive elements. Based on these data, we suggest coevolution of epigenetic promoter elements during the establishment of C4 photosynthesis.