Sleep problems pose global public health concerns, particularly among nurses, with approximately two-thirds experiencing sleep disturbances and fatigue. Although poor sleep hygiene and fatigue can impair nurses' performance and alertness, increasing work-related accidents, chronic diseases, absenteeism, burnout, and medical errors, ultimately threatening both nurses' well-being and patient safety, no studies have been conducted in Ethiopia. This study assesses sleep hygiene practices and perceived fatigue, examines their associations and associated factors among nurses. A cross-sectional study was conducted among 424 nurses via simple random sampling. Data collected using self-administered Sleep Hygiene Index, Chalder Fatigue Scale, and Pittsburgh Sleep Quality Index questionnaires analyzed with SPSS Version 26.0. Bivariate, multivariate, and Pearson correlation analyses were done. The study revealed that 52.3% and 89.3% of nurses had poor sleep hygiene practices, and perceived fatigue respectively. A significant positive correlation was found between poor sleep hygiene and fatigue (r = 0.67, P < 0.001). Burnout syndrome (AOR = 4.51, 95% CI: 2.60, 8.05), depression (AOR = 2.52, 95% CI: 1.53, 4.09), current alcohol drinkers (AOR = 1.95, 95% CI: 1.25, 3.08), shift work sleep disorders (AOR = 2.03, 95% CI: 1.17, 3.82), poor sleep quality (AOR = 5.04,95% CI:2.33,9.52), and job-related stress (AOR = 3.54, 95% CI: 1.76-6.98) were associated factors. Over half of nurses had poor sleep hygiene, and highly experienced perceived fatigue. A significant positive correlation was found between poor sleep hygiene practices and fatigue. Thus, promoting good sleep habits to manage and prevent fatigue among nurses are crucial.