Colorectal cancer (CRC) is one of the most frequent malignancies in the Western world. Early tumor detection and intervention are important determinants on CRC patient survival. During early tumor proliferation, dissemination and angiogenesis, platelets store and segregate proteins actively and selectively. Hence, the platelet proteome is a potential source of biomarkers denoting early malignancy. By comparing protein profiles of platelets between healthy volunteers (n = 12) and patients with early- (n = 7) and late-stage (n = 5) CRCs using multiplex fluorescence two-dimensional gel electrophoresis (2D-DIGE), we aimed at identifying differentially regulated proteins within platelets. By inter-group comparisons, 94 differentially expressed protein spots were detected (p < 0.05) between healthy controls and patients with early- and late-stage CRCs and revealed distinct separations between all three groups in principal component analyses. 54 proteins of interest were identified by mass spectrometry and resulted in high-ranked Ingenuity Pathway Analysis networks associated with Cellular function and maintenance, Cellular assembly and organization, Developmental disorder and Organismal injury and abnormalities (p < 0.0001 to p = 0.0495). Target proteins were validated by multiplex fluorescence-based Western blot analyses using an additional, independent cohort of platelet protein samples [healthy controls (n = 15), early-stage CRCs (n = 15), late-stage CRCs (n = 15)]. Two proteins-clusterin and glutathione synthetase (GSH-S)-featured high impact and were subsequently validated in this independent clinical cohort distinguishing healthy controls from patients with early- and late-stage CRCs. Thus, the potential of clusterin and GSH-S as platelet biomarkers for early detection of CRC could improve existing screening modalities in clinical application and should be confirmed in a prospective multicenter trial.