Background: In the health sector, where demands are high, maintaining physical and mental wellness is a bigger challenge among nurses. Purpose: The study aimed to determine the factors associated with nurses' physical and mental fatigue in the eastern region hospitals of Saudi Arabia. Methods: The study was descriptive, cross-sectional research. 249 nurses from public and private hospitals participated in the study. The Chalder Fatigue Scale (CFQ) was the primary tool utilized for data collection. Mean and standard deviation summarized nurses' demographic characteristics and fatigue levels, while Mann-Whitney U and Kruskal-Wallis were used to compare variables. Results: Nurses revealed a fatigue mean score of 22, SD = 6.47, 35.3% reported more than usual fatigue, while 57.4% experienced usual fatigue. Female nurses, aged 30 to 40, divorced with more years of experience, working extended shifts in private hospitals, and assigned to ICU/CCU, emergency, and surgical units are the factors associated with the physical and mental fatigue of nurses. Conclusion: Strategies such as stress reduction programs, organizational support for the reduction of workload, and targeted interventions on vulnerable groups such as divorced nurses and nurses assigned to surgical units, were endorsed to address the prevalence of work-related fatigue among nurses.