Prostate cancer (PCa) is the second most common diagnosed malignant disease in men worldwide. Although serum PSA test dramatically improved the early diagnosis of PCa, it also led to an overdiagnosis and as a consequence to an overtreatment of patients with an indolent disease. New biomarkers for diagnosis, prediction, and monitoring of the disease are needed. These biomarkers would enable the selection of patients with aggressive or progressive disease and, hence, would contribute to the implementation of individualized therapy of the cancer patient. Since the FDA approval of the long noncoding PCA3 RNA-based urine test for the diagnosis of PCa patients, many new noncoding RNAs (ncRNAs) associated with PCa have been discovered. According to their size and function, ncRNAs can be divided into small and long ncRNAs. NcRNAs are expressed in (tumor) tissue, but many are also found in circulating tumor cells and in all body fluids as protein-bound or incorporated in extracellular vesicles. In these protected forms they are stable and so they can be easily analyzed, even in archival specimens. In this review, the authors will focus on ncRNAs as novel biomarker candidates for PCa diagnosis, prediction, prognosis, and monitoring of therapeutic response and discuss their potential for an implementation into clinical practice.