Gilles de la Tourette syndrome is a neurodevelopmental disorder characterized by motor and vocal tics. It is associated with enhanced processing of stimulus-response associations, including a higher propensity to learn probabilistic stimulus-response contingencies (i.e. statistical learning), the nature of which is still elusive. In this study, we investigated the hypothesis that resting-state theta network organization is a key for the understanding of superior statistical learning in these patients. We investigated the graph-theoretical network architecture of theta oscillations in adult patients with Gilles de la Tourette syndrome and healthy controls during a statistical learning task and in resting states both before and after learning. We found that patients with Gilles de la Tourette syndrome showed a higher statistical learning score than healthy controls, as well as a more optimal (small-world-like) theta network before the task. Thus, patients with Gilles de la Tourette syndrome had a superior facility to integrate and evaluate novel information as a trait-like characteristic. Additionally, the theta network architecture in Gilles de la Tourette syndrome adapted more to the statistical information during the task than in HC. We suggest that hyper-learning in patients with Gilles de la Tourette syndrome is likely a consequence of increased sensitivity to perceive and integrate sensorimotor information leveraged through theta oscillation-based resting-state dynamics. The study delineates the neural basis of a higher propensity in patients with Gilles de la Tourette syndrome to pick up statistical contingencies in their environment. Moreover, the study emphasizes pathophysiologically endowed abilities in patients with Gilles de la Tourette syndrome, which are often not taken into account in the perception of this common disorder but could play an important role in destigmatization.