Building a culturally safe and respectful organisation that genuinely addresses individual and institutional racism is a substantial and complex undertaking. Achieving this outcome requires sustained commitment and a comprehensive strategy, including the active involvement of Aboriginal stakeholders. This paper describes the journey of a large regional health organisation in NSW. A multistrategic approach is broadly described, with three strategies explored in depth. These are: staff education and training; leadership; and consultation, negotiation and partnerships. Challenges are discussed in the context of promising progress and an ongoing commitment to this important organisational goal.