Repetitive transcranial magnetic stimulation (rTMS) treatment of major depressive disorder (MDD) is associated with changes in brain functional connectivity (FC). These changes may be related to the mechanism of action of rTMS and explain the variability in clinical outcome. We examined changes in electroencephalographic FC during the first rTMS treatment in 109 subjects treated with 10 Hz stimulation to left dorsolateral prefrontal cortex. All subjects subsequently received 30 treatments and clinical response was defined as ≥40% improvement in the inventory of depressive symptomatology-30 SR score at treatment 30. Connectivity change was assessed with coherence, envelope correlation, and a novel measure, alpha spectral correlation (αSC). Machine learning was used to develop predictive models of outcome for each connectivity measure, which were compared with prediction based upon early clinical improvement. Significant connectivity changes were associated with clinical outcome (P < 0.001). Machine learning models based on αSC yielded the most accurate prediction (area under the curve, AUC = 0.83), and performance improved when combined with early clinical improvement measures (AUC = 0.91). The initial rTMS treatment session produced robust changes in FC, which were significant predictors of clinical outcome of a full course of treatment for MDD.