Going beyond the focus on isolated brain regions (e.g. amygdala), recent neuroimaging studies on fear conditioning point to the relevance of a network of mutually interacting brain regions. In the present MEG study we used Graph Theory to uncover changes in the architecture of the brain functional network shaped by fear conditioning. Firstly, induced power analysis revealed differences in local cortical excitability (lower alpha and beta power) between CS+ and CS localized to somatosensory cortex and insula. What is more striking however is that the graph theoretical measures unveiled a re-organization of brain functional connections, not evident using conventional power analysis. Subcortical fear-related structures exhibited reduced connectivity with temporal and frontal areas rendering the overall brain functional network more sparse during fear conditioning. At the same time, the calcarine took on a more central role in the network. Interestingly, the more the connectivity of limbic areas is reduced, the more central the role of the occipital cortex becomes. We speculated that both, the reduced coupling in some regions and the emerging centrality of others, contribute to the efficient processing of fear-relevant information during fear learning.