Epigenetic modifications of cytosine residues in DNA and the amino termini of histone proteins have emerged as key mechanisms in chromatin remodeling, impacting both the transcriptional regulation and the establishment of chromosomal domains. Using the chromatin immunoprecipitation (ChIP) assay, we demonstrate that aberrantly silenced genes in cancer cells exhibit a heterochromatic structure that is characterized by histone H3 lysine 9 (H3-K9) hypermethylation and histone H3 lysine 4 (H3-K4) hypomethylation. This aberrant heterochromatin is incompatible with transcriptional initiation but does not inhibit elongation by RNA polymerase II. H3-K9 methylation may, therefore, play a role in the silencing of tumor-suppressor genes in cancer. Treatment with 5-aza-2'-deoxycytidine (5-Aza-CdR), previously known for its ability to inhibit cytosine methylation, induced a rapid and substantial remodeling of the heterochromatic domains of the p14ARF/p16INK4a locus in T24 bladder cancer cells, reducing levels of dimethylated H3-K9 and increasing levels of dimethylated H3-K4 at this locus. In addition, 5-Aza-CdR increased acetylation and H3-K4 methylation at the unmethylated p14 promoter, suggesting it can induce chromatin remodeling independently of its effects on cytosine methylation.