Background: Whilst the globe is facing the second wave of COVID-19 and fears of a potential third wave, patients who were previously infected and recovered from the infection were inadvertently overlooked. Fatigue is one of the most common recognized complaints associated with Coronavirus infection and it has lasted for a variable period after recovery. Objective: To assess the frequency of fatigue post-COVID-19 and whether the period after full recovery and the duration of symptoms affects the severity of fatigue. Method: The current study is a cross-sectional survey. Google form was constructed to build online questionnaires. It included sociodemographic data and the 10 questions of the Fatigue Assessment Scale. Participants were also asked about the duration of symptoms and recovery time. Results: The study enrolled 215 participants. The mean age of the participants was 38.4 ± 12.6 years, 150 females (69.8%) and 65 males (30.2%). The most presenting symptom was bony ache (74.0%). The mean fatigue score was 36.0 and ranged from (12-50). There was no significant association between sociodemographic data items and the fatigue assessment scale. A statistically significant negative association was found between the time after COVID-19 recovery and the Fatigue Assessment Scale. However, there was a statistically significant positive correlation between the duration of symptoms and the Fatigue Assessment Scale. Conclusion: Post-COVID-19 fatigue has been common after recovery from the novel coronavirus infection. The sociodemographic variables did not affect the fatigue score. Prolonged fatigue was associated with a longer duration of symptoms; however, it decreases over time after recovery.