This essay focuses on the 1999 NATO bombing of the Federal Republic of Yugoslavia and explores the process of legitimacy-making-politics in international society. First, it extracts three modes of justification made by NATO leaders, official view, modified version of the official view, and new just war theory, by rearranging their rather confusing and contradictory discourses. It further examines what they implied historically and theoretically in light of the role of the UN Security Council, hierarchy of international norms, and ethics of responsibility. The essay points out that the logics in contemporary international society that justify the NATO bombing are quite new and related to the issues of the universalization of liberal democratic values, revival of just war theory, and general applications of the idea of positive peace, and the growing influence of Western countries led by the United States in international society.