Stroke patients vary considerably in terms of outcomes: some patients present 'natural' recovery proportional to their initial impairment (fitters), while others do not (non-fitters). Thus, a key challenge in stroke rehabilitation is to identify individual recovery potential to make personalized decisions for neuro-rehabilitation, obviating the 'one-size-fits-all' approach. This goal requires (i) the prediction of individual courses of recovery in the acute stage; and (ii) an understanding of underlying neuronal network mechanisms. 'Natural' recovery is especially variable in severely impaired patients, underscoring the special clinical importance of prediction for this subgroup. Fractional anisotropy connectomes based on individual tractography of 92 patients were analysed 2 weeks after stroke (TA) and their changes to 3 months after stroke (TC - TA). Motor impairment was assessed using the Fugl-Meyer Upper Extremity (FMUE) scale. Support vector machine classifiers were trained to separate patients with natural recovery from patients without natural recovery based on their whole-brain structural connectomes and to define their respective underlying network patterns, focusing on severely impaired patients (FMUE < 20). Prediction accuracies were cross-validated internally, in one independent dataset and generalized in two independent datasets. The initial connectome 2 weeks after stroke was capable of segregating fitters from non-fitters, most importantly among severely impaired patients (TA: accuracy = 0.92, precision = 0.93). Secondary analyses studying recovery-relevant network characteristics based on the selected features revealed (i) relevant differences between networks contributing to recovery at 2 weeks and network changes over time (TC - TA); and (ii) network properties specific to severely impaired patients. Important features included the parietofrontal motor network including the intraparietal sulcus, premotor and primary motor cortices and beyond them also attentional, somatosensory or multimodal areas (e.g. the insula), strongly underscoring the importance of whole-brain connectome analyses for better predicting and understanding recovery from stroke. Computational approaches based on structural connectomes allowed the individual prediction of natural recovery 2 weeks after stroke onset, especially in the difficult to predict group of severely impaired patients, and identified the relevant underlying neuronal networks. This information will permit patients to be stratified into different recovery groups in clinical settings and will pave the way towards personalized precision neurorehabilitative treatment.