Prostate adenocarcinoma (PRAD) represents the most common male carcinoma in developed countries, its high relapse risk contributes to the second-leading cause of cancer-related deaths. Therefore, it is required to develop an effective signature for predicting the relapse risk of PRAD. To identify a circadian rhythm- (CR-) related predictive signature, we analyzed RNA-seq data of patients with prostate adenocarcinoma (PRAD) from the TCGA and GEO cohort. Seven circadian rhythm- (CR-) related genes (FBXL22, MTA1, TP53, RORC, DRD4, PPARGC1A, ZFHX3) were eventually identified to develop a CR-related signature. AUCs for 3-year overall survival were 0.852, 0.856 and 0.944 in the training set, validation set and an external independent test set (GSE70768), respectively. Kaplan-Meier curve analysis showed that the high-risk group has a reduced relapse-free survival (RFS) than the low-risk group in the training set, validation set, and test set, respectively (P < 0.05). We constructed a prognostic nomogram combining the CR-related signature with T staging to precisely estimate relapse risk of PRAD patients. Finally, we observed that the CR-related gene signature was associated with tumor mutation burden, multiple immune checkpoint molecules and microsatellite instability, and thus could predict response to immune checkpoint inhibitors in PRAD. Conclusively, we developed a circadian rhythm-related gene signature for predicting RFS and immunotherapy efficacy in prostate adenocarcinoma.