Background Food insecurity underlies and compounds many of the development issues faced by remote Indigenous communities in Australia. Multi-sector approaches offer promise to improve food security. We assessed the feasibility of a novel multi-sector approach to enhance community food security in remote Indigenous Australia. Method A longitudinal comparative multi-site case study, the Good Food Systems Good Food for All Project, was conducted (2009–2013) with four Aboriginal communities. Continuous improvement meetings were held in each community. Data from project documents and store sales were used to assess feasibility according to engagement, uptake and sustainability of action, and impact on community diet, as well as identifying conditions facilitating or hindering these. Results Engagement was established where: the community perceived a need for the approach; where trust was developed between the community and facilitators; where there was community stability; and where flexibility was applied in the timing of meetings. The approach enabled stakeholders in each community to collectively appraise the community food system and plan action. Actions that could be directly implemented within available resources resulted from developing collaborative capacity. Actions requiring advocacy, multi-sectoral involvement, commitment or further resources were less frequently used. Positive shifts in community diet were associated with key areas where actions were implemented. Conclusion A multi-sector participatory approach seeking continuous improvement engaged committed Aboriginal and non-Aboriginal stakeholders and was shown to have potential to shift community diet. Provision of clear mechanisms to link this approach with higher level policy and decision-making structures, clarity of roles and responsibilities, and processes to prioritise and communicate actions across sectors should further strengthen capacity for food security improvement. Integrating this approach enabling local decision-making into community governance structures with adequate resourcing is an imperative.