Indigenous peoples in Australia and similar colonised countries are subject to racism and systemic socioeconomic disadvantages, resulting in worse health outcomes compared to non-Indigenous counterparts. Such inequities persist despite governments' attempts to reduce them. Since 2008, Australian governments have committed to a national 'Closing the Gap' (CTG) to reduce inequities in health, education, and employment outcomes between Aboriginal and Torres Strait Islander peoples and other Australians, but with limited success. We applied policy theory and a cultural safety framework developed for the research to analyse stakeholder perceptions of CTG policy implementation between 2008 and 2019. We identified policy-shaping ideas and policy incoherence in the environment surrounding CTG policy that obstructed culturally safe policy. Topdown, prescriptive modes of implementation were also a barrier. However, Indigenous-led policy partnerships and community-controlled services in the health sector have met principles of cultural safety. Identifying these strengths and weaknesses points to ways in which implementation of CTG policies can be improved to achieve cultural safety and reduce Indigenous health inequities. These results may hold lessons for similar countries such as the United States, New Zealand, and Canada.