Analysis of narrative can help identify the expectations actors hold about each other in international relations. This article triangulates a mix of elite interviews, media content analysis and an original Q-sort public opinion methodology to map the presence of narratives about EU relations among young Israelis and Palestinians. Our aim is not to explain the effects of EU public diplomacy in these countries. Instead we aim to identify the narrative “terrain” or conditions that the EU communicates to and with and, drawing on feminist and everyday narrative studies, to examine the role of affect and identity to explain why some narratives are more “sticky” than others in those societies. We find, first, a broad recognition that the EU’s capacity to act in international relations is necessary but limited in the face of greater challenges in the international system, and indeed, within the EU itself. We find, second, little evidence that young people radically reshape the narratives they encounter in their public spheres, but nevertheless some important divisions emerge that pose problems for how EU policymakers can communicate consistently without dismaying some citizens in third countries.