With the proliferation of international organizations (IOs), legitimacy has become a key for IOs to stay relevant, and to retain their focal places or leadership in the regime complexes. While increasing attention is given to institutional overlap and regime complexity in the international relations literature, there is hardly any work that addresses the question of legitimacy under conditions of overlap. This paper addresses the question: How do International Organizations claim Legitimacy in Complexity? Its main contribution is to present a theoretical framework that unpacks institutional overlap and its implications for legitimation strategies employed by IOs. The relationship between IOs and their environment is theorized in terms of a business environment, where overlapping IOs are compared to business suppliers working in the same market. Borrowing the concepts of competitive advantage and differentiation strategies from the business literature, I argue that in their quest for leadership, IOs react to overlap by employing strategies of legitimation by differentiation (LegD) through which they make use of their competitive advantage. I present an exploratory case in which I analyze the legitimation claims of both the League of Arab States and the African Union in Libyan conflict in 2011 drawing on data from the both organizations’ communiques covering the first year of the Libyan conflict and preliminary data from interviews with a number of former and current officials.