Chronic fatigue (CF) is a distressing symptom that follows cancer treatment; however, it has rarely been studied in hormone-naïve prostate cancer survivors after radical prostatectomy (RP) or definitive radiotherapy (RAD). We investigated CF in prostate cancer survivors after RP or RAD as monotherapy and explored associations between CF and medical and psychosocial variables. A population-based, cross-sectional postal survey in 2006 included Norwegian hormone-naïve survivors with the diagnosis of prostate cancer in 2004 who were treated with RP (n=337) or RAD (n=184). The primary outcome variable was prevalence of CF (defined as fatigue lasting 6 months or longer). Twelve to 32 months after RP and RAD, 13.4 and 26.1% of the patients after, respectively, RP and RAD reported CF inversely associated with pretreatment age (P=0.003). In multivariate analysis, high neuroticism, post-treatment co-morbidity, pain, urinary and intestinal dysfunction, but not sexual dysfunction, were positively associated with reporting CF. Further studies of CF in prostate cancer survivors should take into consideration the survivors' pretreatment medical and psychosocial situation.