Deregulation of long non-coding RNAs (lncRNAs) expression has been proven to be involved in the development and progression of cancer. However, expression pattern and prognostic value of lncRNAs in breast cancer recurrence remain unclear. Here, we analyzed lncRNA expression profiles of breast cancer patients who did or did not develop recurrence by repurposing existing microarray datasets from the Gene Expression Omnibus database, and identified 12 differentially expressed lncRNAs that were closely associated with tumor recurrence of breast cancer patients. We constructed a lncRNA-focus molecular signature by the risk scoring method based on the expression levels of 12 relapse-related lncRNAs from the discovery cohort, which classified patients into high-risk and low-risk groups with significantly different recurrence-free survival (HR = 2.72, 95% confidence interval 2.07-3.57; p = 4.8e-13). The 12-lncRNA signature also represented similar prognostic value in two out of three independent validation cohorts. Furthermore, the prognostic power of the 12-lncRNA signature was independent of known clinical prognostic factors in at least two cohorts. Functional analysis suggested that the predicted relapse-related lncRNAs may be involved in known breast cancer-related biological processes and pathways. Our results highlighted the potential of lncRNAs as novel candidate biomarkers to identify breast cancer patients at high risk of tumor recurrence.