To develop prognostic biomarkers that can discriminate stage II–III colorectal cancer patients with high risk of postoperative recurrence, we conducted a genome-wide screening of relapse-related genes utilizing multiple microarray cohorts. Among differentially expressed genes between tumor and nontumor, we identified eight candidate genes associated with relapse in two datasets of stage II–III patients (n = 94 and 145, respectively, P < 0.05). Using datasets of laser-microdissected samples and FACS-purified cell populations, the localization of candidate genes, including COL4A2, COL4A1, VCAN and SERPINE1, were found predominantly in cancer stroma rather than epithelial components. Among those relapse-related stromal genes, VCAN mRNA, specifically expressed in cancer-associated fibroblasts, was further validated to be a prognostic factor in two additional independent datasets, consisting of 453 (P = 0.0334) and 89 (P = 0.0041) stage II–III patients. Furthermore, in our large set of formalin-fixed paraffin-embedded cohort (n = 338), VCAN protein was detected exclusively in cancer stroma by immunohistochemistry, demonstrating a stepwise increase of stromal VCAN from normal tissues through stage 0 to stage IV tumors. Stromal VCAN protein was associated with shorter relapse-free survival (RFS) in stage II–III colon cancer, independent of other clinical factors by multivariate analysis (P = 0.004). Stratified analyses revealed that stromal VCAN was a strong prognostic indicator particularly in stage II colon cancer (P = 0.0029). In all five analyzed cohorts, the expression of VCAN, in transcript or protein levels, was associated with poor RFS in stage II–III patients. We conclude that VCAN is a promising biomarker to identify stage II–III patients at high risk of relapse who may benefit from intensive postoperative management.