Prostate cancer is one of the most common malignancies in men. It is characterized by a high molecular genomic heterogeneity and, thus, molecular subtypes, that, to date, have not been used in clinical practice. In the present paper, we aimed to better stratify prostate cancer patients through the selection of robust long non-coding RNAs. To fulfill the purpose of the study, a bioinformatic approach focused on feature selection applied to a TCGA dataset was used. In such a way, LINC00668 and long non-coding(lnc)-SAYSD1-1, able to discriminate ERG/not-ERG subtypes, were demonstrated to be positive prognostic biomarkers in ERG-positive patients. Furthermore, we performed a comparison between mutated prostate cancer, identified as “classified”, and a group of patients with no peculiar genomic alteration, named “not-classified”. Moreover, LINC00920 lncRNA overexpression has been linked to a better outcome of the hormone regimen. Through the feature selection approach, it was found that the overexpression of lnc-ZMAT3-3 is related to low-grade patients, and three lncRNAs: lnc-SNX10-87, lnc-AP1S2-2, and ADPGK-AS1 showed, through a co-expression analysis, significant correlation values with potentially druggable pathways. In conclusion, the data mining of publicly available data and robust bioinformatic analyses are able to explore the unknown biology of malignancies.