Why are some institutional designs perceived as more legitimate than others, and why is the same institutional design sometimes perceived as legitimacy-enhancing in one setting and not in another? In a world in which most international organisations (IOs) do not fully embody societal values and norms, such as democratic participation and equal treatment, why do legitimacy deficits in some organisations lead to pressure for institutional change while in others they are tolerated? These are important questions given that many analysts have diagnosed a 'legitimacy crisis' of IOs, but we argue that existing approaches are ill equipped to answer them. We show that the existing legitimacy literature has an implicit model of institutional change-the congruence model-but that this model has difficulty accounting for important patterns of change and non-change because it lacks microfoundations. We argue that attributions of legitimacy rest on perceptions and this implies the need to investigate the cognitive bases of legitimacy. We introduce a cognitive model of legitimacy and deduce a set of testable propositions to explain the conditions under which legitimacy judgments change and, in turn, produce pressures for institutional change in IOs.