For almost three decades, Australia has been locked in a public and political debate about whether and how to ‘recognise’ Aboriginal and Torres Strait Islander peoples in the Australian Constitution. Omnipresent in these debates is the question of sovereignty, over which there is ongoing disagreement, leading to a chronic crisis of legitimacy. In this article, we compare the two substantive recognition reform options that have dominated the contemporary debate: rights and Voice. Recognition through a First Nations Voice is a proposal that, unlike rights, relies on both deliberative and democratic characteristics to address Australia’s legitimacy problems. We identify this as a key reason animating calls for a Voice from First Nations themselves. The Voice, operating as a vehicle through which First Nations can speak directly to the Parliament, has the potential to set up a deliberative and democratic process for the gradual working through of competing legitimacy claims.