Background: After the acute disease, convalescent coronavirus disease 2019 (COVID-19) patients may experience several persistent manifestations that require multidisciplinary pulmonary rehabilitation (PR). By using a machine learning (ML) approach, we aimed to evaluate the clinical characteristics predicting the effectiveness of PR, expressed by an improved performance at the 6-min walking test (6MWT). Methods: Convalescent COVID-19 patients referring to a Pulmonary Rehabilitation Unit were consecutively screened. The 6MWT performance was partitioned into three classes, corresponding to different degrees of improvement (low, medium, and high) following PR. A multiclass supervised classification learning was performed with random forest (RF), adaptive boosting (ADA-B), and gradient boosting (GB), as well as tree-based and k-nearest neighbors (KNN) as instance-based algorithms. Results: To train and validate our model, we included 189 convalescent COVID-19 patients (74.1% males, mean age 59.7 years). RF obtained the best results in terms of accuracy (83.7%), sensitivity (84.0%), and area under the ROC curve (94.5%), while ADA-B reached the highest specificity (92.7%). Conclusions: Our model enables a good performance in predicting the rehabilitation outcome in convalescent COVID-19 patients.