Following a stroke in regions of the brain responsible for motor activity, patients can lose their ability to control parts of their body. Over time, some patients recover almost completely, while others barely recover at all. It is known that lesion volume, initial motor impairment and cortico-spinal tract asymmetry significantly impact motor changes over time. Recent work suggested that disabilities arise not only from focal structural changes but also from widespread alterations in inter-regional connectivity. Models that consider damage to the entire network instead of only local structural alterations lead to a more accurate prediction of patients’ recovery. However, assessing white matter connections in stroke patients is challenging and time-consuming. Here, we evaluated in a data set of 37 patients whether we could predict upper extremity motor recovery from brain connectivity measures obtained by using the patient’s lesion mask to introduce virtual lesions in 60 healthy streamline tractography connectomes. This indirect estimation of the stroke impact on the whole brain connectome is more readily available than direct measures of structural connectivity obtained with magnetic resonance imaging. We added these measures to benchmark structural features, and we used a ridge regression regularization to predict motor recovery at 3 months post-injury. As hypothesized, accuracy in prediction significantly increased (R2 = 0.68) as compared to benchmark features (R2 = 0.38). This improved prediction of recovery could be beneficial to clinical care and might allow for a better choice of intervention.