The burden of colorectal cancer (CRC) is considerable—approximately 1.8 million people are diagnosed each year with CRC and of these about half will succumb to the disease. In the case of CRC, there is strong evidence that an early diagnosis leads to a better prognosis, with metastatic CRC having a 5-year survival that is only slightly greater than 10% compared with up to 90% for stage I CRC. Clearly, biomarkers for the early detection of CRC would have a major clinical impact. We implemented a coherent gel-based proteomics biomarker discovery platform for the identification of clinically useful biomarkers for the early detection of CRC. Potential protein biomarkers were identified by a 2D gel-based analysis of a cohort composed of 128 CRC and site-matched normal tissue biopsies. Potential biomarkers were prioritized and assays to quantitatively measure plasma expression of the candidate biomarkers were developed. Those biomarkers that fulfilled the preset criteria for technical validity were validated in a case-control set of plasma samples, including 70 patients with CRC, adenomas, or non-cancer diseases and healthy individuals in each group. We identified 63 consistently upregulated polypeptides (factor of four-fold or more) in our proteomics analysis. We selected 10 out of these 63 upregulated polypeptides, and established assays to measure the concentration of each one of the ten biomarkers in plasma samples. Biomarker levels were analyzed in plasma samples from healthy individuals, individuals with adenomas, CRC patients, and patients with non-cancer diseases and we identified one protein, tropomyosin 3 (Tpm3) that could discriminate CRC at a significant level (p = 0.0146). Our results suggest that at least one of the identified proteins, Tpm3, could be used as a biomarker in the early detection of CRC, and further studies should provide unequivocal evidence for the real-life clinical validity and usefulness of Tpm3