Climate change poses a serious threat to the health and well-being of Indigenous peoples around the world. Despite living in diverse contexts, Indigenous peoples face a number of common challenges. Disproportionate threats from climate change exist due to a range of factors including unique relationships with the natural environment, socioeconomic deprivation, a greater existing burden of disease, poorer access to and quality of health care, and political marginalization. Responses to climate change at global, national, and local levels also threaten Indigenous people's rights. While climate action presents many opportunities to improve health and reduce inequities, there is also significant potential for climate mitigation and adaptation policies to inflict harm on Indigenous peoples. An important aspect of this is the impact on traditional lands, which are acknowledged as a fundamental determinant of Indigenous health and well-being. This article seeks to elucidate the relationships between climate change and Indigenous health and to inform health promotion solutions to achieve climate justice for Indigenous peoples. The underpinning analysis is founded on a Kaupapa Maori positioning, which seeks transformative change and involves critiquing Western knowledges and structures that undermine Indigenous rights. A central theme is that anthropogenic climate change is intimately connected to the ideologies, systems and practices of colonialism, and that the impacts on Indigenous peoples can be conceptualized as an intensification of the process of colonization. It is not possible to understand and address climate-related health impacts for Indigenous peoples without examining this broader context of colonial oppression, marginalization and dispossession. The challenge for health promotion is to engage in a process of decolonization. This involves deconstructing its own systems and practices to avoid reinforcing colonialism and perpetuating inequities. It also requires health promotion practitioners to support Indigenous self-determination and recognize Indigenous knowledges as a critical foundation for climate change and health solutions.