Community Justice Centres (CJCs) commenced the implementation of an Indigenous-specific mediation service in 2002 in response to a need identified through community research. An initial pilot for the recruitment and training of Indigenous mediators was undertaken in late 2002 in the Northern CJC region, which resulted in the accreditation of 15 Indigenous mediators. An ongoing evaluation of this pilot and the mediation and conflict management services provided by CJCs to Indigenous people and communities commenced in April 2004, with the final evaluation published in June 2006. This article discusses the history of Indigenous mediation within CJCs, and the method and results of the evaluation process. The findings show that the current Indigenous mediation programs conducted by CJCs continue to gain acceptance by Indigenous people and communities throughout NSW. CJCs have committed to flexibility and adaptability within the programs to ensure that the needs of individual communities continue to be met, whilst adhering to the goals and principles of the NSW Aboriginal Justice Plan.