Circulating tumor cells (CTCs) are promising biomarkers that predict progression in patients with advanced cancers. Furthermore, CTC counts are superior to PSA serum measurements in predicting outcome in metastatic prostate cancer (PCa). In contrast, the clinical relevance of CTCs in earlier PCa stages without metastases is unclear. It was therefore unclear if the technologies applied so far were not sensitive enough or if patients with non-metastatic PCa have very low amounts of CTCs and are therefore not suitable for CTC-based liquid biopsies. This is an important question for the biomarker field with implications for future studies trying to detect therapeutic targets or identify resistance mechanisms in earlier PCA stages to block progression to incurable metastatic disease. Here we combined three complementary CTC assays and revealed, for the first time, an unexpectedly high incidence of CTCs in non-metastatic high-risk PCa patients. Furthermore, we could establish reliable protocols for further molecular characterization of CTCs that allow us to identify therapeutic target molecules and resistance mechanisms. Moreover, the analysis of CTCs will provide unique information on the biology of minimal residual disease in PCa patients. CTCs could also represent research tools to personalize treatment by serving as a so-called “liquid biopsy” of an individual's disease. Our findings should help to improve risk assessment and contribute to a better stratification of PCa patients to future additional (adjuvant or salvage) therapies. Although follow-up analysis is still ongoing, the correlation to established risk factors, as demonstrated in this study, suggests a potential clinical relevance of CTCs in non-metastatic PCa. In future clinical trials, more aggressive adjuvant treatment strategies could lead to an improved outcome for CTC positive, high-risk PCa patients.