As highly tissue-specific genes, it is increasingly recognized that long non-coding RNAs (lncRNAs) are considered as promising prognostic biomarkers for multiple human cancers. However, lack of tissue-specific lncRNAs in gastric cancer (GC) still exist. In this study, we identified a novel IncRNA LINC01939 which showed the largest fold change in GC than other human cancers from lnCAR database by bioinformatic analysis. Reverse transcription quantitative polymerase chain reaction (qPCR) assay confirmed that LINC01939 was significantly downregulated in GC tissues compared with matched normal tissues. Low expression of LINC01939 was positively associated with advanced TNM stage and lymphatic metastasis. Patients with low LINC01939 expression have remarkably shorter overall survival (OS) and progression-free survival (PFS) than those with high LINC01939 expression. Univariate and multivariate analysis showed that LINC01939 is an independent protective predictor of OS and PFS in GC patients. Therefore, our data suggest that the newly identified IncRNA LINC01939 might act as a potential prognostic biomarker for GC.