Omics-based molecular signatures can be employed to stratify colorectal cancer (CRC) patients and aid therapeutic treatment or evaluate prognostic outcome. However, reliable molecular biomarkers for identification of patients at risk of relapse are currently lacking. Here, we present a comprehensive multi-omics analysis of a Danish colorectal cancer tumor cohort composed of 371 patients diagnosed at TNM stage II or III. Utilizing proteome profiles, we classified the tumors into four molecular subtypes, including a mesenchymal-like subtype. Mesenchymal-rich tumors are known to represent the most invasive and metastatic phenotype. Therefore, we focused on this subtype protein signature to identify potential relapse risk markers. Among mesenchymal-subtype markers, we followed-up Caveolae-Associated Protein-1 (CAVIN1) and demonstrated its role in tumor progression in a 3D in vitro model of colorectal cancer. Compared to previous CRC studies, our proteomics analysis contributes unique insights into epithelial-to-mesenchymal transition in cancer cells with stronger correlations with risk of relapse.