Despite growing global attention to the development of strategies and policy for climate change adaptation, there has been little allowance for input from Indigenous people. In this study we aimed to improve understanding of factors important in integration of Yolngu perspectives in planning adaptation policy in North East Arnhem Land (Australia). We conducted workshops and in-depth interviews in two 'communities' to develop insight into Yolngu peoples' observations and perspectives on climate change, and their ideas and preferences for adaptation. All participants reported observing changes in their ecological landscape, which they attributed to mining, tourism 'development', and climate change. '. Strange changes' noticed particularly in the last five years, had caused concern and anxiety among many participants. Despite their concern about ecological changes, participants were primarily worried about other issues affecting their community's general welfare. The results suggest that strategies and policies are needed to strengthen adaptive capacity of communities to mitigate over-arching poverty and well-being issues, as well as respond to changes in climate. Participants believed that major constraints to strengthening adaptive capacity had external origins, at regional, state and federal levels. Examples are poor communication and engagement, top-down institutional processes that allow little Indigenous voice, and lack of recognition of Indigenous culture and practices. Participants' preferences for strategies to strengthen community adaptive capacity tended to be those that lead towards greater self-sufficiency, independence, empowerment, resilience and close contact with the natural environment. Based on the results, we developed a simple model to highlight main determinants of community vulnerability. A second model highlights components important in facilitating discourse on enhancing community capacity to adapt to climatic and other stressors. © 2010 Elsevier Ltd.