Prostate cancer is one of the most frequent cancer types among men. Several biomarkers and risk assessment methods are already available; however, enhancing their selectivity and sensitivity is still necessary. For improving therapeutic decisions, both basic and clinical research studies are still ongoing for a better understanding of the underlying molecular mechanisms. The enzymatic digests of heparan sulfate (HS) and chondroitin sulfate (CS) chains were investigated in tissue samples taken from patients with prostate cancer (PCa) and benign prostate hyperplasia (BPH) with the HPLC–MS methodology. None of the HS species analyzed showed correlating alterations with currently used markers such as clinical stage, Gleason score, or prostate-specific antigen (PSA) level. The total quantity and sulfation motifs of CS were both significantly different among BPH and different risk groups of PCa. Furthermore, the cancer-specific survival of patients can be predicted based on the levels of non-sulfated and doubly sulfated CS disaccharides as well as the total HS content and the doubly and triply sulfated HS disaccharide ratios. These disaccharide ratios proved to be independent markers from clinical parameters. Further investigations of glycosaminoglycan motifs were proposed for the validation of the results on independent patient cohorts as well.