The Declaration on the Rights of Indigenous Peoples passed the United Nations General Assembly on September 13, 2007. This document articulates the minimum international standard on indigenous peoples' rights that nation states are obligated to recognize and protect. It took more than thirty years of intense effort by the indigenous rights movement to achieve passage of the Declaration. This dissertation explores how indigenous politics at the global level compels a new direction of thought in International Relations. I argue that indigenous global politics is a perspective of International Relations that complicates the structure of international politics in new and important ways, challenging both Westphalian notions of state sovereignty and the (neo-)liberal foundations of states and the international system. A case study of the international indigenous peoples' movement and the development of the United Nations Declaration on the Rights of Indigenous Peoples demonstrates how attempts to secure indigenous rights at the international level are helping to forge new articulations of the concepts of sovereignty, the state, and territoriality. I have also detected a peculiar pattern of state response to these changes, a pattern that was previously undetected, unexamined and thus also unnamed in International Relations. I have termed this puzzling pattern "over-compliance," by which I mean that a state's indigenous rights policy behavior goes above and beyond its international commitments. My qualitative case studies of Canadian and New Zealand indigenous rights "over-compliance," based on original field research, analyze both the potential and the limits of the challenges posed by indigenous global politics. My research identifies several mechanisms that explain both legal "over-compliance" with treaty standards and de facto policy under-compliance, including the domestic and international strength of transnational indigenous movements and coalitions, and changes within a state's domestic political discourse regarding indigenous reconciliation.