Background Colorectal cancer (CRC) is a major cause of death worldwide. Sensitive, non-invasive diagnostic screen methods are urgently needed to improve its survival rates. Stable circulating microRNA offers unique opportunities for the early diagnosis of several diseases, including cancers. Our aim has been to find new plasma miRNAs that can be used as biomarkers for the detection of CRC. Methodology/Principal Findings According to the results of miRNA profiling performed on pooling plasma samples form 10 CRC patients or 10 healthy controls, a panel of miRNAs (hsa-miR-10a, -19a, -22*, -24, -92a, 125a-5p, -141, -150, -188-3p, -192, -210, -221, -224*, -376a, -425*, -495, -572, -601, -720, -760 and hsa-let-7a, -7e) were deregulated in CRC plasma with fold changes >5. After large scale validation by qRT-PCR performed on another 191 independent individuals (90 CRC, 43 advanced adenoma and 58 healthy participants), we found that the levels of plasma miR-601 and miR-760 were significantly decreased in colorectal neoplasia (carcinomas and advanced adenomas) compared with healthy controls. ROC curve analysis showed that plasma miR-601 and miR-760 were of significant diagnostic value for advanced neoplasia. These two miRNAs together yield an AUC of 0.792 with 83.3% sensitivity and 69.1% specificity for separating CRC from normal controls, and yield an AUC of 0.683 with 72.1% sensitivity and 62.1% specificity in discriminating advanced adenomas from normal controls. Conclusions/Significance Plasma miR-601 and miR-760 can potentially serve as promising non-invasive biomarkers for the early detection of CRC.