Development of castration-resistant prostate cancer (CRPC) is associated with alterations in gene expression involved in steroidogenesis and androgen signaling. This study investigates whether gene expression changes related to CRPC development can be identified in circulating tumor cells (CTCs). Gene expression in paired CTC samples from 29 patients, before androgen deprivation therapy (ADT) and at CRPC relapse, was compared using a panel including 47 genes related to prostate cancer progression on a qPCR platform. Fourteen genes displayed significantly changed gene expression in CTCs at CRPC relapse compared to before start of ADT. The genes with increased expression at CRPC relapse were related to steroidogenesis, AR-signaling, and anti-apoptosis. In contrast, expression of prostate markers was downregulated at CRPC. We also show that midkine (MDK) expression in CTCs from metastatic hormone-sensitive prostate cancer (mHSPC) was associated to short cancer-specific survival (CSS). In conclusion, this study shows that gene expression patterns in CTCs reflect the development of CRPC, and that MDK expression levels in CTCs are prognostic for cancer-specific survival in mHSPC. This study emphasizes the role of CTCs in exploring mechanisms of therapy resistance, as well as a promising biomarker for prognostic and treatment-predictive purposes in advanced mHSPC.