Abstract Analyses of alterations of brain networks have gained an increasing interest in stroke rehabilitation research. Compared with functional networks derived from resting-state analyses, there is limited knowledge of how structural network topology might undergo changes after stroke and, more importantly, if structural network information obtained early after stroke could enhance recovery models to infer later outcomes. The present work re-analysed cross-sectional structural imaging data, obtained within the first 2 weeks, of 45 acute stroke patients (22 females, 24 right-sided strokes, age 68 ± 13 years). Whole-brain tractography was performed to reconstruct structural connectomes and graph-theoretical analyses were employed to quantify global network organization with a focus on parameters of network integration and modular processing. Graph measures were compared between stroke patients and 34 healthy controls (15 females, aged 69 ± 10 years) and they were integrated with four clinical scores of the late subacute stage, covering neurological symptom burden (National Institutes of Health Stroke Scale), global disability (modified Rankin Scale), activity-related disability (Barthel Index) and motor functions (Upper-Extremity Score of the Fugl-Meyer Assessment). The analyses were employed across the complete cohort and, based on clustering analysis, separately within subgroups stratified in mild to moderate (n = 21) and severe (n = 24) initial deficits. The main findings were (i) a significant reduction of network’s global efficiency, specifically in patients with severe deficits compared with controls (P = 0.010) and (ii) a significant negative correlation of network efficiency with the extent of persistent functional deficits at follow-up after 3–6 months (P ≤ 0.032). Specifically, regression models revealed that this measure was capable to increase the explained variance in future deficits by 18% for the modified Rankin Scale, up to 24% for National Institutes of Health Stroke Scale, and 16% for Barthel Index when compared with models including the initial deficits and the lesion volume. Patients with mild to moderate deficits did not exhibit a similar impact of network efficiency on outcome inference. Clustering coefficient and modularity, measures of segregation and modular processing, did not exhibit comparable structure–outcome relationships, neither in severely nor in mildly affected patients. This study provides empirical evidence that structural network efficiency as a graph-theoretical marker of large-scale network topology, quantified early after stroke, relates to recovery. Notably, this contribution was only evident in severely but not mildly affected stroke patients. This suggests that the initial clinical deficit might shape the dependency of recovery on global network topology after stroke.