Resting-state functional MRI activity is organized as a complex network. However, this coordinated brain activity changes with time, raising questions about its evolving temporal arrangement. Does the brain visit different configurations through time in a random or ordered way? Advances in this area depend on developing novel paradigms that would allow us to shed light on these issues. We here propose to study the temporal changes in the functional connectome by looking at transition graphs of network activity. Nodes of these graphs correspond to brief whole-brain connectivity patterns (or meta-states), and directed links to the temporal transition between consecutive meta-states. We applied this method to two datasets of healthy subjects (160 subjects and a replication sample of 54), and found that transition networks had several non-trivial properties, such as a heavy-tailed degree distribution, high clustering, and a modular organization. This organization was implemented at a low biological cost with a high cost-efficiency of the dynamics. Furthermore, characteristics of the subjects’ transition graphs, including global efficiency, local efficiency and their transition cost, were correlated with cognition and motor functioning. All these results were replicated in both datasets. We conclude that time-varying functional connectivity patterns of the brain in health progress in time in a highly organized and complex order, which is related to behavior.