Background: Primary tumor sidedness has been found to be prognostic in colorectal cancer (CRC), with right-sided colon cancer (RCC) having a worse survival than left-sided tumors (LCC), even after controlling for known negative prognostic factors. Our previous proteomic study identified differences in protein profiles between LCC and RCC. Immune-related proteins were found to be up-regulated in LCC while the differentially expressed proteins in RCC were mainly enriched in extracellular matrix-related proteins. Herein we aim to construct a prognostic prediction model for LCC and RCC patients by using immune-related genes (IRGs) and extracellular matrix-related genes (ECMGs). Methods: A total of 1,868 CRC patients with complete follow-up data from 1 training cohort (n = 562) and 3 independent validation cohorts (n = 622, n = 403, n = 281, respectively) were enrolled in our study. Tumors located in the splenic flexure, descending colon, sigmoid colon, and rectum are defined as LCC. In contrast, tumors located in the region from the hepatic flexure to the cecum are defined as RCC. The Least Absolute Shrinkage and Selection Operator (LASSO) algorithm was used to construct the multi-gene signatures. Univariate and multivariate analyses were used to test the prognostic value of these models. Results: Our biomarker discovery effort identified a 9-gene IRGs signature that significantly associated with poor DFS for LCC (HR = 3.46, 95%CI = 2.38-5.01, P < 0.001) and a 21-gene ECMGs signature associated with prognosis for RCC (HR = 4.53, 95%CI = 2.84-7.22, P < 0.001). For LCC, the IRGs signature was significantly correlated with worse prognosis in three independent validation cohort (Validation-1 cohort: HR = 2.08, 95%CI = 1.41-3.09, P < 0.001; Validation-2 cohort: HR = 2.19, 95%CI = 1.26-3.81, P = 0.004; Validation-3 cohort: HR = 2.94, 95%CI = 1.53-5.63, P < 0.001). Similarly, the ECMGs signature also robustly predicted survival for RCC in three independent validation (Validation-1 cohort: HR = 1.86, 95%CI = 1.22-2.83, P = 0.003; Validation-2 cohort: HR = 1.96, 95%CI = 1.18-3.26, P = 0.008; Validation-3 cohort: HR = 2.8, 95%CI = 1.27-6.17, P = 0.007). When compared with Oncotype DX, we found IRGs achieved an improved survival correlation in LCC (C-index, validation-3 cohort: 0.75 vs 0.64) and ECMGs got a better survival correlation in RCC (C-index, validation-3 cohort: 0.74 vs 0.58). Conclusions: Combing a 9-gene IRGs signature for LCC and a 21-gene ECMGs signature for RCC, we established a prognostic model that can robustly stratify CRC patients into high- and low- risk groups of tumor recurrence and predict prognosis.