Recurrence in major depressive disorder (MDD) is common, but neurobiological models capturing vulnerability for recurrences are scarce. Disturbances in multiple resting-state networks have been linked to MDD, but most approaches focus on stable (vs. dynamic) network characteristics. We investigated how the brain's dynamical repertoire changes after patients transition from remission to recurrence of a new depressive episode. Sixty two drug-free, MDD-patients with ≥2 episodes underwent a baseline resting-state fMRI scan when in remission. Over 30-months follow-up, 11 patients with a recurrence and 17 matched-remitted MDD-patients without a recurrence underwent a second fMRI scan. Recurrent patterns of functional connectivity were characterized by applying Leading Eigenvector Dynamics Analysis (LEiDA). Differences between baseline and follow-up were identified for the 11 non-remitted patients, while data from the 17 matched-remitted patients was used as a validation dataset. After the transition into a depressive state, basal ganglia-anterior cingulate cortex (ACC) and visuo-attentional networks were detected significantly more often, whereas default mode network activity was found to have a longer duration. Additionally, the fMRI signal in the basal ganglia-ACC areas underlying the reward network, were significantly less synchronized with the rest of the brain after recurrence (compared to a state of remission). No significant changes were observed in the matched-remitted patients who were scanned twice while in remission. These findings characterize changes that may be associated with the transition from remission to recurrence and provide initial evidence of altered dynamical exploration of the brain's repertoire of functional networks when a recurrent depressive episode occurs.