This article tries to illuminate political dynamics of international legitimacy-making, by looking at the discourses of NATO leaders concerning their legitimizing efforts for its bombing campaign against Serbia in 1999. It classifies justifications for the intervention into three types, the official view of NATO headquarters, the modified version of the official view, and a new just war theory, which respectively contain deep theoretical and historical backgrounds. Then the article examines issues involved in each justification: NATO's official explanation and the role of the Security Council, the modified official view and the hierarchy of norms, and new just war theory and the ethics of responsibility. The concluding remarks highlight the characteristics of new international legitimacy-making in the context of liberalism, just war, positive peace, and the dominance of the West in contemporary international society.