In the western world, colorectal cancer (CRC) is the third most common cause of cancer-related deaths. Survival is closely related to the stage of cancer at diagnosis striking the clinical need for biomarkers capable of early detection. To search for possible biological parameters for early diagnosis of CRC we evaluated protein expression for three CREC (acronym: Cab45, reticulocalbin, ERC-55, calumenin) proteins: reticulocalbin, calumenin, and ERC-55 in a cellular model consisting of a normal derived colon mucosa cell line, NCM460, and a primary adenocarcinoma cell line of the colon, SW480. Furthermore, this cellular model was analyzed by a top-down proteomic approach, 2-dimensional polyacrylamide gel electrophoresis (2D-PAGE) and liquid chromatography–tandem mass spectrometry (LC–MS/MS) for novel putative diagnostic markers by identification of differentially expressed proteins between the two cell lines. A different colorectal carcinoma cell line, HCT 116, was used in a bottom-up proteomic approach with label-free quantification (LFQ) LC–MS/MS. The two cellular models gave sets of putative diagnostic CRC biomarkers. Various of these novel putative markers were verified with increased expression in CRC patient neoplastic tissue compared to the expression in a non-involved part of the colon, including reticulocalbin, calumenin, S100A6 and protein SET. Characterization of these novel identified biological features for CRC patients may have diagnostic potential and therapeutic relevance in this malignancy characterized by a still unmet clinical need.