Colorectal cancer (CRC) is one of the most leading causes of cancer deaths worldwide. In the study, we aimed to identify key long non-coding RNAs (lncRNAs) significantly associated with prognosis of CRC and develop an expression-based lncRNA signature to provide survival risk prediction for CRC patients. LncRNA expression profiles and clinical information of CRC patients were collected from The Cancer Genome Atlas (TCGA) database. Six hundred and eighteen differentially expressed lncRNAs were identified between CRC and normal tissues. After univariate and multivariate Cox regression analysis for these differentially expressed lncRNAs and overall survival of CRC patients, six predictive lncRNAs (RP1-170O19.17, RP11-785D18.3, RP11-798K3.2, XXbac-B476C20.9, RP11-481J13.1, and RP11-167H9.4) were finally screened out to construct a six-lncRNA signature, based on which patients in the training dataset were divided into the high-risk and low-risk group with significantly different overall survival. ROC curve analysis demonstrated competitive performance of the six-lncRNA signature. The prognostic power of the six-lncRNA signature was successfully validated in the testing and entire dataset. Multivariate Cox regression analysis and stratification analysis further suggested that the six-lncRNA signature was independent of other conventional clinical variables for survival prediction in CRC patients. Functional enrichment analysis revealed the possible roles of these predictive lncRNAs in some cancer-related biological processes and pathways. Our study demonstrated the promising potential of the novel six-lncRNA signature as an independent biomarker for survival prediction of CRC patients.