Stroke is a leading cause of adult disability. Understanding stroke damage and recovery requires deciphering changes in complex brain networks across different spatiotemporal scales. While recent developments in brain readout technologies and progress in complex network modeling have revolutionized current understanding of the effects of stroke on brain networks at a macroscale, reorganization of smaller scale brain networks remains incompletely understood. In this review, we use a conceptual framework of graph theory to define brain networks from nano- to macroscales. Highlighting stroke-related brain connectivity studies at multiple scales, we argue that multiscale connectomics-based approaches may provide new routes to better evaluate brain structural and functional remapping after stroke and during recovery.