De novo methylation of CpG islands is a common phenomenon in human cancer, but the mechanisms of cancer-associated DNA methylation are not known. We have used tiling arrays in combination with the methylated CpG island recovery assay to investigate methylation of CpG islands genome-wide and at high resolution. We find that all four HOX gene clusters on chromosomes 2, 7, 12, and 17 are preferential targets for DNA methylation in cancer cell lines and in early-stage lung cancer. CpG islands associated with many other homeobox genes, such as SIX, LHX, PAX, DLX, and Engrailed, were highly methylated as well. Altogether, more than half (104 of 192) of all CpG island-associated homeobox genes in the lung cancer cell line A549 were methylated. Analysis of paralogous HOX genes showed that not all paralogues undergo cancer-associated methylation simultaneously. The HOXA cluster was analyzed in greater detail. Comparison with ENCODE-derived data shows that lack of methylation at CpG-rich sequences correlates with presence of the active chromatin mark, histone H3 lysine-4 methylation in the HOXA region. Methylation analysis of HOXA genes in primary squamous cell carcinomas of the lung led to the identification of the HOXA7- and HOXA9-associated CpG islands as frequent methylation targets in stage 1 tumors. Homeobox genes are potentially useful as DNA methylation markers for early diagnosis of the disease. The finding of widespread methylation of homeobox genes lends support to the hypothesis that a substantial fraction of genes methylated in human cancer are targets of the Polycomb complex.