DNA hypermethylation of the p15INK4b tumor suppressor gene is commonly observed in acute myeloid leukemia (AML). Repressive histone modifications and their associated binding proteins have been implicated in the regulation of DNA methylation and the transcriptional repression of genes with DNA methylation. We have used high-density chromatin immunoprecipitation-on-chip to determine the histone modifications that normally regulate p15INK4b expression in AML cells and how these marks are altered in cells that have p15INK4b DNA methylation. In AML patient blasts without p15INK4b DNA methylation, a bivalent pattern of active (H3K4me3) and repressive (H3K27me3) modifications exist at the p15INK4b promoter. AML patient blasts with p15INK4b DNA methylation lose H3K4me3 at p15INK4b and become exclusively marked by H3K27me3. H3K27me3, as well as EZH2, extends throughout p14ARF and p16INK4a, indicating that polycomb repression of p15INK4b is a common feature in all AML blasts irrespective of the DNA methylation status of the gene. Reactivation of p15INK4b expression in AML cell lines and patient blasts using 5-aza-2'-deoxycytidine (decitabine) and trichostatin A increased H3K4me3 and maintained H3K27me3 enrichment at p15INK4b. These data indicate that AML cells with p15INK4b DNA methylation have an altered histone methylation pattern compared with unmethylated samples and that these changes are reversible by epigenetic drugs.