Using a bioinformatics-based strategy, we set out to identify hypermethylated genes that could serve as biomarkers for early detection of colorectal cancer (CRC) in stool. In addition, the complementary value to a Fecal Immunochemical Test (FIT) was evaluated. Candidate genes were selected by applying cluster alignment and computational analysis of promoter regions to microarray-expression data of colorectal adenomas and carcinomas. DNA methylation was measured by quantitative methylation-specific PCR on 34 normal colon mucosa, 71 advanced adenoma, and 64 CRC tissues. The performance as biomarker was tested in whole stool samples from in total 193 subjects, including 19 with advanced adenoma and 66 with CRC. For a large proportion of these series, methylation data for GATA4 and OSMR were available for comparison. The complementary value to FIT was measured in stool subsamples from 92 subjects including 44 with advanced adenoma or CRC. Phosphatase and Actin Regulator 3 (PHACTR3) was identified as a novel hypermethylated gene showing more than 70-fold increased DNA methylation levels in advanced neoplasia compared with normal colon mucosa. In a stool training set, PHACTR3 methylation showed a sensitivity of 55% (95% CI: 33-75) for CRC and a specificity of 95% (95% CI: 87-98). In a stool validation set, sensitivity reached 66% (95% CI: 50-79) for CRC and 32% (95% CI: 14-57) for advanced adenomas at a specificity of 100% (95% CI: 86-100). Adding PHACTR3 methylation to FIT increased sensitivity for CRC up to 15%. PHACTR3 is a new hypermethylated gene in CRC with a good performance in stool DNA testing and has complementary value to FIT.