Background/objectives: Considering the diverse symptomatology of COVID-19—ranging from mild to severe cases—multi-professional interventions are crucial for enhancing physical recovery, nutritional status, and mental health outcomes in affected patients. Thus, this study aimed to investigate the effects of such an intervention on health-related physical fitness and biomarkers in overweight COVID-19 survivors with varying degrees of symptom severity after 8 weeks and 16 weeks. Methods: This non-randomized clinical trial included 59 overweight COVID-19 survivors (32 males and 27 females) divided into three groups: mild (n = 31), moderate (n = 13), and severe/critical (n = 15). The participants underwent a multi-professional program and were assessed for anthropometric and body composition (primary outcome), as well as physical fitness and biochemical markers (secondary outcome) 8 and 16 weeks before the intervention. Results: After 8 weeks, time effects were observed for the maximum isometric handgrip strength (p < 0.001), maximum isometric lumbar-traction strength (p = 0.01), flexibility (p < 0.001), abdominal strength–endurance (p < 0.001), the sit-and-stand test (p < 0.001), maximum oxygen consumption (p < 0.001), and distance covered in the 6 min walk test (p < 0.001). Additionally, time effects were also observed for fat mass (p = 0.03), body fat percentage (p = 0.02), abdominal circumference (p = 0.01), total cholesterol (p < 0.001), low-density lipoproteins (p < 0.001), and glycated hemoglobin (p < 0.001), with lower values after multi-professional interventions. After 16 weeks, the systolic and diastolic blood pressure showed significant reductions independently of the intervention group (p < 0.001). Conclusion: These findings suggest that multi-professional interventions can provide substantial benefits for post-COVID-19 patients, regardless of the severity of their initial symptoms.