Coastal northern Australia is largely owned and occupied by Aboriginal people who are strongly connected to their traditional country. We assess the views of Aboriginal people in Arnhem Land on the impacts of climate change and their possible precautionary responses to both sea level rise and a potential increase in the intensity of tropical cyclones in coastal communities. All respondents had heard about climate change, and 48 % had already seen environmental changes, particularly sea level rise, which they attributed to climate change. Fifty-eight percent of respondents would consider relocating in the future for safety reasons, although most respondents perceived living close to the sea as highly important for their future well-being, emphasising their strong connection to their traditional sea country. Many of those willing to relocate would consider moving inland, either temporarily or permanently, provided that community facilities could also be moved. Other respondents who said they would be unlikely to relocate in the future because of climate change impacts, and would prefer to adapt in situ with government support (e. g. building more shelters for severe cyclones, building sea walls and better roads for quick evacuation if necessary). We recommend that the diversity of adaptation preferences among Aboriginal people should be accommodated in policy to minimise social impacts of climate change and to take advantage of potential opportunities that could arise from moving.