Climate change directly threatens Indigenous cultures and livelihoods across Australia's Murray-Darling Basin (MDB). Using a modified grounded theory methodology, this study draws on in-depth interviews with Indigenous leaders and elders across the MDB to highlight that climate variability and over-extraction of water resources by agricultural users directly threatens the integrity of aquatic systems. As a consequence, Indigenous cultures and livelihoods reliant on these natural systems are at risk. Interviewees identify a range of systemic barriers that entrench vulnerability of Indigenous Peoples (IPs) in the MDB. Building on insights from the literature and from interviews, a Recognition, Empowerment and Devolution (RED) framework is developed to establish possible pathways to support climate adaptation by rural IPs. Fundamental to this RED framework is the need for non-Indigenous socio-institutional structures to create a 'space' to allow IPs the ability to adapt in their own ways to climate impacts.