Indigenous primary health care (PHC) services have been identified as exemplary models of comprehensive PHC; however, many practitioners in these services struggle to deliver effective health promotion. In particular, practitioners have limited capacity and resources to evaluate health promotion activities. Best practice health promotion is important to help address the lifestyle and wider factors that impact on the health of people and communities. In this paper, we report on the acceptability and feasibility of an innovative approach for evaluating the design of health promotion activities in four Indigenous PHC services in the Northern Territory. The approach draws on a popular continuous quality improvement technique known as audit and feedback (A&F), in which information related to best practice is gathered through the use of a standardised audit tool and fed back to practitioners. The A&F approach has been used successfully to improve clinical service delivery in Indigenous PHC; however, the technique has had limited use in health promotion. The present study found that facilitated participatory processes were important for the collection of locally relevant information and for contributing to improving PHC practitioners' knowledge and understanding of best practice health promotion.