Proteome-centric studies, although have identified numerous lncRNA-encoded polypeptides, lack differential expression analysis of lncRNA-peptidome across primary tissues, cell lines and cancer states. We established a computational-proteogenomic workflow involving re-processing of publicly available LC-MS/MS data, which facilitated the identification of tissue-specific and universally expressed (UExp) lncRNA-polypeptides across 14 primary human tissues and 11 cell lines. The utility of lncRNA-peptidome as cancer-biomarkers was investigated by re-processing LC-MS/MS data from 92 colon-adenocarcinoma (COAD) and 30 normal colon-epithelium tissues. Intriguingly, a significant upregulation of five lncRNA UExp-polypeptides in COAD tissues was observed. Furthermore, clustering of the UExp-polypeptides led to the classification of COAD patients that coincided with the clinical stratification, underlining the prognostic potential of the UExp-polypeptides. Lastly, we identified differential abundance of the UExp-polypeptides in the plasma of prostate-cancer patients highlighting their potential as plasma-biomarker. The analysis of lncRNA-peptidome may pave the way to identify effective tissue/plasma biomarkers for different cancer types.