Prostate cancer (PCa) is the most common cancer among men in developed countries. Although its genetic background is thoroughly investigated, rather little is known about the role of small non-coding RNAs (sncRNA) in this disease. tRNA-derived fragments (tRFs) represent a new class of sncRNAs, which are present in a broad range of species and have been reported to play a role in several cellular processes. Here, we analyzed the expression of tRFs in fresh frozen patient samples derived from normal adjacent prostate and different stages of PCa by RNA-sequencing. We identified 598 unique tRFs, many of which are deregulated in cancer samples when compared to normal adjacent tissue. Most of the identified tRFs are derived from the 5'- and 3'-ends of mature cytosolic tRNAs, but we also found tRFs produced from other parts of tRNAs, including pre-tRNA trailers and leaders, as well as tRFs from mitochondrial tRNAs. The 5'-derived tRFs comprise the most abundant class of tRFs in general and represent the major class among upregulated tRFs. The 3'-derived tRFs types are dominant among downregulated tRFs in PCa. We validated the expression of three tRFs using qPCR. The ratio of tRFs derived from tRNALysCTT and tRNAPheGAA emerged as a good indicator of progression-free survival and a candidate prognostic marker. This study provides a systematic catalogue of tRFs and their dysregulation in PCa and can serve as the basis for further research on the biomarker potential and functional roles of tRFs in this disease.