De novo metastatic or recurrence of prostate cancer (PC) remains life-threatening. Circulating tumor cells (CTCs) are noninvasive biomarkers and provide unique information that could enable tailored treatment. This study evaluated the impact of CTCs in PC patients eligible for peptide vaccine therapy. Twenty-seven patients were tested for CTCs with the CellCollector® device (Detector CANCER01(DC01)) during short-term androgen deprivation therapy (ADT) before cancer vaccine treatment (cohort 1) or salvage radiation (cohort 2). CTC counts were compared to clinicopathological parameters. In cohort 1, CTCs were correlated to immune responses, serum protein profiles, and clinical outcomes. In cohort 2, captured CTCs were further profiled for expression of PSMA, PAP, and PD-L1. Nine out of 22 patients (40.9%) in cohort 1 were CTC positive. These patients demonstrated vaccine-specific immune response (p = 0.009) and long-term prostate cancer-specific survival (log-rank, p = 0.008). All five patients in cohort 2 had CTCs at recurrence (count range 18–31), and 4/5 had CTCs positive for PSMA, PAP, and PD-L1. The DC01 CTC detection provides information beyond current clinical practice. Despite the small size of cohort 1, a correlation between CTC detection and outcome was shown.