Issue addressed The study examined effective ways to build the capacity of health organisations and professionals in the public health sector to reduce Aboriginal chronic disease risk factors. It investigated the capacity-building strategies of the Victorian Aboriginal Community Controlled Health Organisation (VACCHO) nutrition team in the facilitation of the statewide implementation of the Victorian Aboriginal Nutrition and Physical Activity Strategy 2009-2014 (VANPAS). Methods Using a qualitative design, the study analysed the VACCHO program from 2009-2014 across five domains of capacity development: workforce, resources, organisations, partnerships and leadership. Data were sourced from archival program documents and 62 semi-structured participant interviews. Results Diverse Aboriginal and non-Aboriginal professional, organisation representatives and community participants engaged in the implementation of the VANPAS. The VACCHO team used the VANPAS to solidify participant buy-in, strengthen workforce effectiveness, increase health promotion and resource appropriateness, improve organisational policy and build an evidence-base through collaborative dialogue using action-reflection principles. Conclusion A credible, high-profile Aboriginal community led and evidence-based statewide program and a commitment to dialogue through action-reflection provided a meaningful basis for both Aboriginal community and mainstream organisational engagement. Upon this foundation, the VACCHO team built a coherent sectoral system with increased capacity to enhance the nutrition of Aboriginal Victorians. So what? In an historical context of mistrust and unmet expectations, program implementation methods that build confidence amongst collaborating Aboriginal and non-Aboriginal health agencies is fundamental to building capacity to enhance Aboriginal nutrition and health.