Background: Patients with Philadelphia chromosome-negative Myeloproliferative Neoplasms (MPNs) report fatigue as the most common symptom and contributing significantly to reduction in their quality of life (QoL). Targeted non-pharmacological intervention to increase levels of physical activity is suggested as a fatigue-reducing and QoL-enhancing intervention in MPN patients. The interrelationship between physical activity, fatigue, and QoL has, to our knowledge, never been reported. Methods: We analyzed data from 1807 MPN patients. The primary analysis included a multiple regression model allowing fatigue to mediate the relationship between physical activity and QoL. Results: We herein report the first and the largest study of patients with MPNs, in whom we have investigated the interrelationship between fatigue, physical activity, and QoL. Sedentary patients were more likely to report fatigue compared to highly active patients. There was a negative association between fatigue and QoL, and there was a positive association between physical activity and QoL. There was no interaction between fatigue and physical activity in the association with QoL. Conclusion: We found positive associations between level of physical activity and QoL, independently of fatigue being present. More research is needed before physical activity can be introduced as a targeted intervention to reduce fatigue and increase QoL in the management of patients.