Australia's governance arrangements for natural resource management (NRM) have evolved considerably over the last 30 years. The impact of changes in governance on NRM planning and delivery requires assessment. We undertake a multi-method programme evaluation using adaptive governance principles as an analytical frame and apply this to Queensland to assess the impacts of governance change on NRM planning and governance outcomes. Data to inform our analysis includes: (1) a systematic review of 16 audits/evaluations of Australian NRM over a 15-year period; (2) a review of Queensland's first-generation NRM plans; and (3) outputs from a Queensland workshop on NRM planning. NRM has progressed from a bottom-up grassroots movement into a collaborative regional NRM model that has been centralised by the Australian government. We found that while some adaptive governance challenges have been addressed, others remained unresolved. Results show that collaboration and elements of multi-level governance under the regional model were positive moves, but also that NRM arrangements contained structural deficiencies across multiple governance levels in relation to public involvement in decision-making and knowledge production for problem responsiveness. These problems for adaptive governance have been exacerbated since 2008. We conclude that the adaptive governance framework for NRM needs urgent attention so that important environmental management problems can be addressed.