Since colorectal cancer (CRC) remains one of the most common malignancies, a tremendous amount of studies keep taking place in this field. Over the past 25 years, a notable part of the scientific community has focused on the association between the immune system and colorectal cancer. A variety of studies have shown that high densities of infiltrating CD8+ T-cells are associated with improved disease-free and overall survival in CRC. Stromal cell-derived factor-1 (SDF-1) is a protein that regulates leukocyte trafficking and is variably expressed in several healthy and malignant tissues. There is strong evidence that SDF-1 has a negative prognostic impact on a variety of solid tumors. However, the existing data do not provide sufficient evidence that the expression of SDF-1 has an influence on CRC. Knowing nowadays, that the microenvironment plays a crucial role in the development of cancer, we hypothesized that the expression of SDF-1 in CRC could influence the prognostic significance of CD8+ T-cells, as an indicator of the essential role of the immune microenvironment in cancer development. Therefore, we explored the combined prognostic significance of CD8+ T-cell density and SDF-1 expression in a large CRC collective. We analyzed a tissue microarray of 613 patient specimens of primary CRCs by immunohistochemistry (IHC) for the CD8 + T-cells density and the expression of SDF-1 by tumor cells and tumor-infiltrating immune cells. Besides, we analyzed the expression of SDF-1 at the RNA level in The Cancer Genome Atlas cohort. We found that the combined high CD8+ T-cell infiltration and expression of SDF-1 shows a favorable 5-year overall survival rate (66%; 95% CI 48-79%) compared to tumors showing a high expression of CD8+ T-cell only (55%; 95% CI 45-64%; p = 0.0004). After stratifying the patients in nodal negative and positive groups, we found that the prognostic significance of CD8+ T-cell density in nodal positive colorectal cancer depends on SDF-1 expression. Univariate and multivariate Hazard Cox regression survival analysis considering the combination of both markers revealed that the combined high expression of SDF-1 and CD8+ T-cell density was an independent, favorable, prognostic marker for overall survival (HR = 0.34, 95% CI 0.17-0.66; p = 0.002 and HR = 0.45, 95% CI 0.23-0.89; p = 0.021, respectively). In our cohort there was a very weak correlation between SDF-1 and CD8+ T-cells (rs = 0.13, p = 0.002) and in the trascriptomic expression of these two immune markers display a weak correlation (rs = 0.28, p < 0.001) which was significantly more pronounced in stage III cancers (rs = 0.40, p < 0.001). The combination of high CD8+ T-cell density and expression of SDF-1 represents an independent, favorable, prognostic condition in CRC, mostly in patients with stage III disease.