The disruption of genomic DNA methylation patterns was the first epigenetic abnormality to be described in human cancer. This imbalance involves the promoter CpG island hypermethylation of tumor-suppressor genes, causing transcriptional repression, and global genomic hypomethylation, leading to chromosomal instability and reactivation of endoparasitic sequences. The relationship between DNA methylation and histone modifications was initially described in the context of the inactivation of female X chromosomes and of the demonstration of strong interactions between the DNA methylation machinery and chromatin modifiers. The repression of tumor-suppressor genes by promoter hypermethylation was also found to be associated with a specific histone modification index. However, this jigsaw was missing a piece: a global view of how the histone modification landscape was distorted in cancer cells. We have recently discovered this piece of the puzzle, demonstrating that the association between DNA methylation and histone modification aberrations in cancer also occurs at the global level. In human and mouse tumors, histone H4 undergoes a loss of monoacetylated and trimethylated lysines 16 and 20, respectively. Most importantly, these alterations occur within the context of the repetitive DNA sequences that also become hypomethylated in transformed cells. The global alterations of histone acetylation status suggest novel pathways by which histone acetyltransferases (HATs), histone methyltransferases (HMTs), and histone deacetylases (HDACs) may play roles as tumor-suppressor genes or oncogenes. In this regard, we have shown how the generation of particular fusion proteins involving HATs in leukemias is associated with an erasure of the monoacetylated lysine 16-H4 marker, whilst the loss of trimethylation at lysine 20-H4 disrupts heterochromatic domains and may reduce the response to DNA damage of cancer cells.