(1) Background: Cardiopulmonary and brain functions are frequently impaired after COVID-19 infection. Exercise rehabilitation could have a major impact on the healing process of patients affected by long COVID-19. (2) Methods: The COVID-Rehab study will investigate the effectiveness of an eight-week cardiopulmonary rehabilitation program on cardiorespiratory fitness (V˙Omax) in long-COVID-19 individuals. Secondary objectives will include functional capacity, quality of life, perceived stress, sleep quality (questionnaires), respiratory capacity (spirometry test), coagulation, inflammatory and oxidative-stress profile (blood draw), cognition (neuropsychological tests), neurovascular coupling and pulsatility (fNIRS). The COVID-Rehab project was a randomised clinical trial with two intervention arms (1:1 ratio) that will be blindly evaluated. It will recruit a total of 40 individuals: (1) rehabilitation: centre-based exercise-training program (eight weeks, three times per week); (2) control: individuals will have to maintain their daily habits. (3) Conclusions: Currently, there are no specific rehabilitation guidelines for long-COVID-19 patients, but preliminary studies show encouraging results. Clinicaltrials.gov (NCT05035628).