In partnership with the Aboriginal Health and Medical Research Council of NSW (AH&MRC), the NSW Ministry of Health is developing a 10-year Aboriginal Health Plan for NSW. Recent reports have highlighted the need for significant systemic and structural change, coupled with genuine engagement with Aboriginal people. A whole health-system approach has been adopted and is examining all the interdependent and influencing elements that impede or facilitate effective health outcomes for Aboriginal people. The collaboration will develop a new strategic framework that will provide clear direction concerning how we address Aboriginal health in NSW. We have done this by seeking genuine engagement and partnership with Aboriginal people, organisations and communities. A phased approach has been used to develop the Plan. This paper describes the first phase of a two-phased approach. A discussion paper was released on National Close the Gap Day, 22 March 2012.