In 2016, President Ing-wen Tsai apologized to the Taiwanese indigenous peoples on behalf of the government, which is known as the National Apology. Echoing this National Apology, the Council of Indigenous Peoples reaffirmed its proposal called the “substantive negotiation process”. Before long, this innovative treaty-making provision opened a debate on whether or not such process can really fit in with Taiwan’s current constitutional and legal system. As a way to move forward, this article attempts to scrutinize similar treaty debates in Australia. In doing so, it has become more clear that treaty-making, (indigenous) sovereignty, and the Constitution are not separate issues, but rather, a connected one. As treaty forms the basic relationships between government/state and indigenous peoples, the debate itself is about the fundamental question of power-sharing and decolonization. Given that the government often treats treaty-making as a way of legitimatizing its power, this article cautions that indigenous peoples must stay alert to the possible harms of treaty-making. There is always a danger that buying into coloniser’s concept, i.e. treaty or sovereignty, could sink the whole indigenous struggle into the frameworks of the settler’s/state’s logic.