Abstract Background Indigenous Australians have significantly poorer status on a large range of health, educational and socioeconomic measures and successive Australian governments at state and federal level have committed to redressing these disparities. Despite this, improvements in Aboriginal health status have been modest, and Australia has much greater disparities in the health of its Indigenous people compared to countries that share a history characterised by colonisation and the dispossession of indigenous populations such as New Zealand, Canada and the United States of America. Efforts at policy and planning must ultimately be translated into practical strategies. This article outlines an approach that was effective in Western Australia in increasing the engagement and concern of Aboriginal people about high rates of sexually transmissible infections and sexual health issues. Many aspects of the approach are relevant for other health issues. Results The complexity of Indigenous sexual health necessitates inter-agency and cross-governmental collaboration, in addition to Aboriginal leadership, accurate data, and community support. A recent approach covering all these areas is described. This has resulted in Aboriginal sexual health being more actively discussed within Aboriginal health settings than it once was and additional resources for Indigenous sexual health being available, with better communication and partnership across different health service providers and sectors. The valuable lessons in capacity building, collaboration and community engagement are readily transferable to other health issues, and may be useful for other health professionals working in the challenging area of Aboriginal health. Conclusion Health service planners and providers grapple with achieving Aboriginal ownership and leadership regarding their particular health issue, despite sincere concern and commitment to addressing Aboriginal health issues. This highlights the need to secure genuine Aboriginal engagement. Building capacity that enables Indigenous people and communities to fulfill their own goals is a long-term strategy and requires sustained commitment, but we argue is a prerequisite for better Indigenous health outcomes.