Indigenous Australians have higher levels of mental illness, self-harm, suicide and substance abuse than non-Indigenous Australians, as well as more frequent contact with the criminal justice system. These indices point to the need for strong leadership to support Close the Gap programmes that have now been implemented across Australia. This article considers leadership as a journey of learning for Australian Indigenous leaders. Through the use of story, it is suggested that a situational leadership approach, incorporating the principles of mindfulness, provides the most appropriate framework for Indigenous leaders who work with Indigenous communities. Flexible approaches are needed to meet the needs of diverse Indigenous populations, and address the complex challenges involved, including lateral violence. Such flexibility will enable Indigenous leaders and communities to work together to achieve improvements in the health outcomes, not only for Indigenous Australians, but also for Indigenous populations worldwide.