Background: Colorectal carcinoma (CRC) is a heterogeneous disease, and differences in outcomes have been reported among patients diagnosed with the same disease stage. Prognostic and predictive biomarkers provide information for patient risk stratification and guide treatment selection. Although numerous studies have analyzed the effects of systemic inflammatory factors on CRC outcomes, clinical significance remains to be elucidated. In particular, the treatment strategy of colon cancer patients is different from that of rectal cancer due to outcome and recurrence differences. The identification of patients with a poor prognosis who might benefit from intensive treatment approaches is clinically necessary. Methods: This study aimed to evaluate the value of different blood-based markers and assess the significance of our newly developed inflammatory-nutrition-related biomarker (NCR = BMI × albumin/CRP) in patients with colon cancer. A two-stage design was used with 212 patients with colon cancer (CC) in the discovery cohort (n = 159) and in an external validation cohort (n = 53). Results: A lower preoperative NCR level was significantly correlated with a worse prognosis, sidedness, undifferentiated histology, nodal involvement, and advanced UICC stage. We compared the NCR with other established prognostic indices and showed that the NCR is a more reliable indicator of a poor prognosis for patients with CC. Patients with low NCR levels experienced a significantly shorter Overall Survival (OS) than patients with high levels. Multivariate analysis confirmed preoperative NCR levels as an independent predictor for overall survival with a hazard ratio of 3.3 (95% confidence interval 1.628–6.709, p < 0.001). Finally, we confirmed the predictive value of the NCR in an independent validation cohort and confirmed NCR as an independent prognostic factor for OS. Conclusion: Taken together, we discovered a new prognostic index (NCR) based on BMI, albumin, and CRP levels as an independent prognostic predictor of OS in patients with colon cancer. In all UICC stages, our newly developed NCR marker is able to distinguish patients with better and worse prognoses. We, therefore, propose that NCR may serve as a supplement to the TNM staging system to optimize the risk stratification in CC patients towards personalized oncology. In particular, NCR can be used in clinical trials to stratify patients with UICC II and III tumors and help better select patients who might benefit from adjuvant treatment.