Background: Colorectal cancer (CRC) is the second leading cause of cancer deaths despite the fact that detection of this cancer in early stages results in over 90% survival rate. Currently less than 45% of at-risk individuals in the US are screened regularly, exposing a need for better screening tests. We performed two case-control studies to validate a blood-based test that identifies methylated DNA in plasma from all stages of CRC. Methodology/Principal Findings: Using a PCR assay for analysis of Septin 9 (SEPT9) hypermethylation in DNA extracted from plasma, clinical performance was optimized on 354 samples (252 CRC, 102 controls) and validated in a blinded, independent study of 309 samples (126 CRC, 183 controls). 168 polyps and 411 additional disease controls were also evaluated. Based on the training study SEPT9-based classification detected 120/252 CRCs (48%) and 7/102 controls (7%). In the test study 73/126 CRCs (58%) and 18/183 control samples (10%) were positive for SEPT9 validating the training set results. Inclusion of an additional measurement replicate increased the sensitivity of the assay in the testing set to 72% (90/125 CRCs detected) while maintaining 90% specificity (19/183 for controls). Positive rates for plasmas from the other cancers (11/96) and non-cancerous conditions (41/315) were low. The rate of polyp detection (>1 cm) was ∼20%. Conclusions/Significance: Analysis of SEPT9 DNA methylation in plasma represents a straightforward, minimally invasive method to detect all stages of CRC with potential to satisfy unmet needs for increased compliance in the screening population. Further clinical testing is warranted.