Cortical thickness and gyrification abnormalities in anorexia nervosa (AN) have been recently described, but no attempt has been made to explore their organizational patterns to characterize the neurobiology of the disorder in the different stages of its course. The aim of this study was to explore cortical thickness and gyrification patterns by means of graph theory tools in 38 patients with AN, 20 fully recovered patients, and 38 healthy women (HC). All participants underwent high-resolution magnetic resonance imaging. Connectome properties were compared between: 1) AN patients and HC, 2) fully recovered patients and HC, 3) patients with a full remission at a 3-year follow-up assessment and patients who had not recovered. Small-worldness was greater in patients with acute AN in comparison to HC in both cortical thickness and gyrification networks. In the cortical thickness network, patients with AN also showed increased Local Efficiency, Modularity and Clustering coefficients, whereas integration measures were lower in the same group. Patients with a poor outcome showed higher segregation measures and lower small-worldness in the gyrification network, but no differences emerged for the cortical thickness network. For both cortical thickness and gyrification patterns, regional analyses revealed differences between patients with different outcomes. Different patterns between cortical thickness and gyrification networks are probably due to their peculiar developmental trajectories and sensitivity to environmental influences. The role of gyrification network alterations in predicting the outcome suggests a role of early maturational processes in the prognosis of AN.