Background: A limited number of studies have exclusively assessed fatigue among post-COVID patients. Our study aimed to assess the persistence and associations of fatigue among COVID-19 survivors after two months of recovery from their primary illness. Method: During hospital admission from August to September, 2020, a total of 373 patients were diagnosed to be suffering from fatigue using Chalder fatigue scale. After obtaining informed written consent, patients were followed up two months later over telephone. A total of 332 participants participated in the interview (36 patients could not be traced and another 5 patient died within two months). Patients were asked to categorize their present fatigue condition based on a simplified questionnaire developed for telephone interview. Result: Among study participants, 62.9% (n=207) were found to be still suffering from fatigue two months after their hospital discharge. A significant association of fatigue was found with age (p=0.000), hypertension (RR: 1.51; CI: 1.15-1.99; p=0.002), diabetes mellitus (RR: 1.45; CI: 1.08-1.95; p=0.010), ischemic heart disease (RR: 2.04; CI: 1.15-3.64; p=0.011), on admission SpO2 (p=0.000), on admission serum ferritin (p=0.000), d-dimer (p=0.000), CRP (p=0.000), and Hb% (p=0.019). Binary logistic regression model revealed significant association of age and on-admission SpO2 with persistence of fatigue. Conclusion: Fatigue is a highly prevalent symptom among the COVID-19 survivors with significant association between fatigue and patients clinical and laboratory markers.