Accelerated intermittent theta burst stimulation (aiTBS) is a noninvasive neurostimulation technique that shows promise for improving clinical outcome in patients suffering from treatment-resistant depression (TRD). Although it has been suggested that aiTBS may evoke beneficial neuroplasticity effects in neuronal circuits, the effects of aiTBS on brain networks have not been investigated until now. Fifty TRD patients were enrolled in a randomized double-blind sham-controlled crossover trial involving aiTBS, applied to the left dorsolateral prefrontal cortex. Diffusion-weighted MRI data were acquired at each of three time points (T1 at baseline; T2 after the first week of real/sham aiTBS stimulation; and T3 after the second week of treatment). Graph analysis was performed on the structural connectivity to examine treatment-related changes in the organization of brain networks. Changes in depression severity were assessed using the Hamilton Depression Rating Scale (HDRS). Baseline data were compared with 60 healthy controls. We observed a significant reduction in depression symptoms over time (p < 0.001). At T1, both TRD patients and controls exhibited a small-world topology in their white matter networks. More importantly, the TRD patients demonstrated a significantly shorter normalized path length (pAUC = 0.01), and decreased assortativity (pAUC = 0.035) of the structural networks, compared with the healthy control group. Within the TRD group, graph analysis revealed a less modular network configuration between T1 and T2 in the TRD group who received real aiTBS stimulation in the first week (p < 0.013). Finally, there were no significant correlations between changes on HDRS scores and reduced modularity. Application of aiTBS in TRD is characterized by reduced modularity, already evident 4 days after treatment. These findings support the potential clinical application of such noninvasive brain stimulation in TRD.