Recent developments in graph theory have heightened the need for investigating the disruptions in the topological structure of functional brain network in major depressive disorder (MDD). In this study, we employed resting-state functional magnetic resonance imaging (fMRI) and graph theory to examine the whole-brain functional networks among 42 MDD patients and 42 healthy controls. Our results showed that compared with healthy controls, MDD patients showed higher local efficiency and modularity. Furthermore, MDD patients showed altered nodal centralities of many brain regions, including hippocampus, temporal cortex, anterior cingulate gyrus and dorsolateral prefrontal gyrus, mainly located in default mode network and cognitive control network. Together, our results suggested that MDD was associated with disruptions in the topological structure of functional brain networks, and provided new insights concerning the pathophysiological mechanisms of MDD.