How do international organizations (IOs) and their proponents claim legitimacy, and how do their opponents undermine such legitimacy? This article develops a framework that accounts for the links between legitimation and delegitimation strategies and how they regularly produce ‘legitimation struggles’. Drawing on the case of the African Union between 2015–2020, the study goes beyond existing research in three ways. First, legitimation struggles are not simply related to input and output legitimacy but are deeply related to the social purpose of the organization. Second, legitimation struggles do not only involve IO representatives and member-states but are strengthened by a range of other non-state agents. Third, while discursive strategies are essential, legitimation struggles are reinforced when they are combined with behavioural or institutional legitimation strategies. Future research would do well to go beyond the current Western-centric bias and draw on our findings to investigate legitimation struggles under different conditions around the world.