Background Fatigue and sleep disturbance are 2 of the most common and distressing cancer symptoms that negatively affect quality of life. Objective The aim of this study was to assess the prevalence of, and factors contributing to, fatigue and sleep disturbance in Arabic-speaking cancer patients in Oman after completion of their cancer treatment. Methods A cross-sectional and descriptive correlational design was used. Data were collected using the Pittsburgh Sleep Quality Index where a score of >5 indicated as poorer sleep, the Functional Assessment of Cancer Therapy–Fatigue a score of ≤34 indicating clinically significant fatigue, and the Functional Assessment of Cancer Therapy–General. Results Of the 369 patients who participated, 77.5% (n = 286) reported clinically significant fatigue, and 78% (n = 288) reported poor sleep. Fatigue (P < .05) was significantly associated with age, cancer site, months since diagnosis, type of treatment received, and comorbidity. Those experiencing fatigue and poor sleep had the lowest quality of life among the cancer patients studied. Conclusion Fatigue and sleep disturbance are significant problems for the Arabic patients diagnosed with cancer. Both fatigue and sleep disturbance should be routinely assessed in the case of such patients. Implications for Practice Routine assessments of fatigue and sleep disturbance are recommended so that appropriate interventions and treatment management plans can be introduced to reduce fatigue and improve sleep quality among patients with cancer.