In this study, we used the ESTIMATE algorithm to analyze clinical data and transcriptome profiles of 1635 colorectal cancer (CRC) samples from the Gene Expression Omnibus and The Cancer Genome Atlas databases and identify prognostic immune-related genes (IRGs). We identified 941 differentially expressed (4 downregulated and 937 upregulated) genes by comparing samples with high and low immune, stromal scores and tumor purity. LASSO Cox regression analyses showed that the risk score based on a ten-IRG signature was an independent prognostic factor in CRC. The nomogram with pathological stages (TNM) and the ten-IRG signature showed a C-index of 0.769 (95% CI, 0.717-0.821), and area under ROC curve values of 0.788, 0.782 and 0.789 for 1-, 3-, and 5-year OS, respectively. TIMER database analysis showed positive correlation between the ten prognostic IRGs and the levels of tumor-infiltrated immune cells, including CD4+ and CD8+ T cells, macrophages, neutrophils, and dendritic cells. These findings demonstrate that this novel ten-IRG signature correlates with the pathological stages and the levels of multiple tumor-infiltrated immune cell types. This makes the ten-IRG signature a potential prognostic factor for CRC patients.