Cognitive and emotional functions are supported by the coordinated activity of a distributed network of brain regions. This coordinated activity may be disrupted by psychosocial stress, resulting in the dysfunction of cognitive and emotional processes. Graph theory is a mathematical approach to assess coordinated brain activity that can estimate the efficiency of information flow and determine the centrality of brain regions within a larger distributed neural network. However, limited research has applied graph-theory techniques to the study of stress. Advancing our understanding of the impact stress has on global brain networks may provide new insight into factors that influence individual differences in stress susceptibility. Therefore, the present study examined the brain connectivity of participants that completed the Montreal Imaging Stress Task (Goodman et al., 2016; Wheelock et al., 2016). Salivary cortisol, heart rate, skin conductance response, and self-reported stress served as indices of stress, and trait anxiety served as an index of participant’s disposition toward negative affectivity. Psychosocial stress was associated with a decrease in the efficiency of the flow of information within the brain. Further, the centrality of brain regions that mediate emotion regulation processes (i.e., hippocampus, ventral prefrontal cortex, and cingulate cortex) decreased during stress exposure. Interestingly, individual differences in cortisol reactivity were negatively correlated with the efficiency of information flow within this network, whereas cortisol reactivity was positively correlated with the centrality of the amygdala within the network. These findings suggest that stress reduces the efficiency of information transfer and leaves the function of brain regions that regulate the stress response vulnerable to disruption.