Since 2009, the Belgian Archaeological Mission to Elkab of the Royal Museums of Art and History is excavating the remains of a large settlement that has its origin in the Badarian period. During the excavation season of 2012, the distal end of an obsidian flake was found in the early Naqada II horizon of test pit 3. The geochemical analysis of its trace elements indicates that this flake, like other analysed samples from Hierakonpolis and Naqada, originates from obsidian sources in the Ethiopian Afar triangle. The Elkab flake brings additional data to the existing corpus of provenanced obsidian fragments and the discussion on possible exchange routes. Based on the archaeological context, the geographical and chronological distribution of all known obsidian objects, combined with new data emerging from recent and intensive archaeological research in the deserts south and west of the Egyptian Nile Valley, the question of these exchange routes needs to be reconsidered within a broader framework of various simultaneous supply networks. In this paper, we propose to break down the procurement of obsidian in early Egypt in two phases that also highlight some of the socio-economic developments occurring during the Predynastic period and the changes following the formation of the Egyptian state.