This article examines a leadership paradox at the heart of EU foreign policy between the demand for effective European leadership, and leadership legitimacy embedded in state practices. This paradox is manifested in the Lisbon treaty that delegated significant formal leadership functions to the European level. We probe the question how and by whom leadership can and should be performed in EU foreign policy. To answer this question, we advance a new theoretical framework drawing on sociological institutionalism and role theory. We argue that leadership should be understood as a social role shaped in a process of interaction between leader and followers. We contribute with new empirical knowledge of leadership role relations based on an interview survey conducted in 2016. The empirical results point to role conflicts over the formal leadership functions in EU foreign policy and the emergence of new informal leadership practices by EU member states.