The genome of epithelial tumors is characterized by numerous chromosomal aberrations, DNA base sequence changes, and epigenetic abnormalities. The epigenome of cancer cells has been most commonly studied at the level of DNA CpG methylation. In squamous cell carcinomas of the lung, CpG methylation patterns undergo substantial changes relative to normal lung epithelium. Using a genome-scale mapping technique for CpG methylation (MIRA-chip), we characterized CpG island methylation and methylation patterns of entire chromosome arms at a level of resolution of approximately 100 bp. In individual stage I lung carcinomas, several hundred and probably up to a thousand CpG islands become methylated. Interestingly, a large fraction (almost 80%) of the tumor-specifically methylated sequences are targets of the Polycomb complex in embryonic stem cells. Homeobox genes are particularly overrepresented and all four HOX gene loci on chromosomes 2, 7, 12, and 17 are hotspots for tumor-associated methylation because of the presence of multiple methylated CpG islands within these loci. DNA hypomethylation at CpGs in squamous cell tumors preferentially affects repetitive sequence classes including SINEs, LINEs, subtelomeric repeats, and segmental duplications. Since these epigenetic changes are found in early stage tumors, their contribution to tumor etiology as well as their potential usefulness as diagnostic or prognostic biomarkers of the disease should be considered.