International institutions are facing increasing criticism of the legitimacy of their authority. But what does it mean for an international institution to be legitimate? Arthur Applbaum’s latest book provides a convincing new concept of legitimacy, namely, the power-liability view, and a new normative conception, the free group agent account. However, it is not clear how they can be applied to the international level. First, this paper examines how different concepts of legitimacy can be applied to international institutions. Second, it assesses three different conceptions of legitimacy, namely, the service conception, Applbaum’s free group agent account and the autonomy-based conception for the international level. It outlines how on the last conception, international institutions’ legitimacy depends on three different aspects required to protect autonomy: the political power of the institution; its purpose; and its relation to other institutions. Finally, the paper argues that the creation of an international institution should be seen as part of relational legitimacy and that state consent plays an important role to protect the political autonomy of peoples.