Background: A hallmark of cancer cells is hypermethylation of CpG islands (CGIs), which probably arises from upregulation of one or more DNA methyltransferases. The purpose of this study was to identify the targets of DNMT3B, an essential DNA methyltransferase in mammals, in colon cancer. Methodology/Principal Findings: Chromatin immunoprecipitation with DNMT3B specific antibody followed by CGI micro array identified genes with or without CGIs, repeat elements and genomic contigs in RKO cells. ChIP-Chop analysis showed that the majority of the target genes including P16, DCC, DISC1, SLIT1, CAVEOLIN1, GNA11, TBX5, TBX18, HOXB13 and some histone variants, that harbor CGI in their promoters, were methylated in multiple colon cancer cell lines but not in normal colon epithelial cells. Further, these genes were reactivated in RKO cells after treatment with 5-aza-2'-deoxycytidine, a DNA hypomethylating agent. COBRA showed that the CGIs encompassing the promoter and/or coding region of DCC, TBX5, TBX18, SLIT1 were methylated in primary colorectal tumors but not in matching normal colon tissues whereas GNA11 was methylated in both. Mass ARRAY analysis demonstrated that the CGI located,~4.5 kb upstream of HOXB13 +1 site was tumor-specifically hypermethylated in primary colorectal cancers and cancer cell lines. HOXB13 upstream CGI was partially hypomethylated in DNMT1-/- HCT cells but was almost methylation free in cells lacking both DNMT1 and DNMT3B. Analysis of tumor suppressor properties of two aberrantly methylated transcription factors, HOXB13 and TBX18, revealed that both inhibited growth and clonogenic survival of colon cancer cells in vitro, but only HOXB13 abolished tumor growth in nude mice. Conclusions/Significance: This is the first report that identifies several important tumor suppressors and transcription factors as direct DNMT3B targets in colon cancer and as potential biomarkers for this cancer. Further, this study shows that methylation at an upstream CGI of HOXB13 is unique to colon cancer.