This chapter examines the view that state creation requires the existence of a normatively legitimate government. It begins by defining governmental legitimacy, arguing that it is best analysed in terms of the moral justifiability of individual acts of governance, whether viewed individually or in aggregate. Next, it considers what it means for institutions, social conventions, and legal principles to be legitimate before moving on to consider the negative argument that no theory of state creation that excludes a criterion of governmental legitimacy could ever be morally plausible. Having dismissed this objection as mistaken, the chapter then examines a range of legitimacy-based reconstructions, which draw respectively upon the philosophy of Thomas Hobbes, Immanuel Kant, and John Locke. Each position is critiqued and dismissed as an implausible approach to the law of state creation.