The relationship between legitimacy and justice is highly contentious within the literature on just(ified) international violence – be it with regard to matters of national self-defense, the authority to start a revolution or humanitarian intervention. Whereas scholars of International Relations emphasize the need to rely on established political procedures, moral philosophers often dismiss these procedures (and especially the workings of the UN Security Council) entirely, pointing to the suboptimal outcomes in terms of an ideal theory of “deep” morality. This paper argues that the only fruitful way out of this conundrum consists in trying to reform existing institutions in ways that pay tribute to substantial matters of justice and morality, but hold on to the procedural idea of public reason. In the end, this necessitates developing a more robust conception of legitimacy that combines procedural and substantial issues.