Objective: Fear of recurrence (FOR) is a key concern among survivors of all cancers. In prostate cancer, FOR varies with health and treatment type, but little is known about how survivors' appraisals of their treatment, and in particular, their level of regret over treatment decisions may affect this. Methods: A total of 1229 prostate cancer survivors between 2‐ and 5‐years postdiagnosis were invited to complete a postal questionnaire including a FOR scale, Decisional Regret Scale, and the European Organization for Research and Treatment of Cancer QLQ C30 health‐related quality of life (HRQoL) instrument. Multiple regression analysis explored the impact of 3 blocks of factors on FOR: (1) demographic characteristics and disease extent, (2) primary treatment received and health status (treatment side effects and HRQoL), and (3) treatment appraisals, specifically satisfaction with information received regarding treatment and level of regret experienced over treatment decisions. Results: The final multivariable model explained 27% of variance on FOR. Significant correlates of lower FOR included having localised disease, having undergone an invasive treatment, as well as health status (higher HRQoL and fewer ongoing side effects). Beyond this, appraisals of treatment significantly contributed to the model: More decisional regret and lower satisfaction with information received were associated with higher FOR. Conclusion: These findings suggest that FOR may be mitigated by providing survivors with more information regarding treatment choices and the treatment itself so that men can make well‐informed decisions and experience less future regret. Sensitivity analysis for variables predicting FOR among prostate cancer survivors is not suspected of having a recurrence.