The European Union (EU) has been struggling to find a shared course on African migration since the entry into force of the Schengen Agreement (1995). It has done so through two interrelated processes of negotiation. To begin, parties have negotiated internal and external migration policies. In addition, they have negotiated narrative frames about migration and whether migration should be interpreted rather as an opportunity or as a threat. In times in which narrative frames increasingly shape policy negotiations, it becomes very important to analyse how policymakers negotiate narrative frames on migration and how these shape policy responses. However, such an analysis is still missing. This article investigates how the negotiation of EU policies on African migration from 1999 until 2019 has been influenced by a simultaneous process of negotiation of narrative frames on migration. It does so based on policy analysis and interviews with European and African policymakers. It finds two major trends in EU negotiation processes: migration-security narratives have strengthened national-oriented approaches, and migration-development narratives have strengthened transnational-oriented approaches. The two approaches have always been interlinked. However, in the last years, security-oriented national approaches have increasingly influenced development-oriented transnational approaches.