Magnetic resonance imaging studies have reported significant functional and structural differences between depressed patients and controls. Little attention has been given, however, to the abnormalities in anatomical connectivity in depressed patients. In the present study, we aim to investigate the alterations in connectivity of whole-brain anatomical networks in those suffering from major depression by using machine learning approaches. Brain anatomical networks were extracted from diffusion magnetic resonance images obtained from both 22 first-episode, treatment-naive adults with major depressive disorder and 26 matched healthy controls. Using machine learning approaches, we differentiated depressed patients from healthy controls based on their whole-brain anatomical connectivity patterns and identified the most discriminating features that represent between-group differences. Classification results showed that 91.7% (patients = 86.4%, controls = 96.2%; permutation test, p<0.0001) of subjects were correctly classified via leave-one-out cross-validation. Moreover, the strengths of all the most discriminating connections were increased in depressed patients relative to the controls, and these connections were primarily located within the cortical-limbic network, especially the frontal-limbic network. These results not only provide initial steps toward the development of neurobiological diagnostic markers for major depressive disorder, but also suggest that abnormal cortical-limbic anatomical networks may contribute to the anatomical basis of emotional dysregulation and cognitive impairments associated with this disease.