This paper constructs the African Union (AU) claim of sovereignty within the debate among international relations scholars about change and continuity in “institutions” and “structures” of the international system. I develop a theory of change: internationalization of authority transformed international organizations (IOs) into state structures possessing sovereignty as transferred authority. Dominant IOs, like the UN, are legitimated by constituent structures, including regional organizations. But there has been a legitimation crisis as the constituent structures oppose dominant IOs’ legitimacy. The rules of IO legitimation must comprise a complete representation of constituent structures in decision-making organs and the alignment of norms, values, priorities, interests, or goals with constituent structures. Noncompliance with these rules will cause fundamental changes. I base the theory on constructivist accounts of change. Specifically, the sovereignty framework, which I expand using studies on IO authority and legitimacy, internationalization of the state, the third image of structure, and new regionalism.