In the Near East, nomadic hunter-gatherer societies became sedentary farmers for the first time during the transition into the Neolithic. Sedentary life presented a risk of isolation for Neolithic groups. As fluid intergroup interactions are crucial for the sharing of information, resources and genes, Neolithic villages developed a network of contacts. In this paper we study obsidian Exchange between Neolithic villages in order to characterize this network of interaction. Using agent-based modelling and elements taken from complex network theory, we model obsidian exchange and compare results with archaeological data. We demonstrate that complex networks of interaction were established at the outset of the Neolithic and hypothesize that the existence of these complex networks was a necessary condition for the success and spread of a new way of living.