Cancer related fatigue (CRF) is a common and debilitating symptom that can influence quality of life (QoL) in cancer patients. The increase in survival times stresses for a better understanding of how CRF affects patients’ QoL. This was a cross-sectional descriptive study with 148 randomly recruited prostate cancer patients aiming to explore CRF and its impact on QoL. Assessments included the Cancer Fatigue Scale, EORTC QLQ-C30, and EORTC QLQ-PR25. Additionally, 15 in-depth structured interviews were performed. Quantitative data were analyzed with simple and multiple regression analysis and independent samples -test. Qualitative data were analyzed with the use of thematic content analysis. The 66.9% of the patients experienced CRF with higher levels being recorded for the affective subscale. Statistically significant differences were found between the patients reporting CRF and lower levels of QoL (mean = 49.1) and those that did not report fatigue and had higher levels of QoL (mean = 72.1). The interviews emphasized CRF’s profound impact on the patients’ lives that was reflected on the following themes: “dependency on others,” “loss of power over decision making,” and “daily living disruption.” Cancer related fatigue is a significant problem for patients with advanced prostate cancer and one that affects their QoL in various ways.