Background: In recent decades, financial investment has been made in health-related programs and services to overcome inequities and improve Indigenous people's wellbeing in Australia and New Zealand. Despite policies aiming to 'close the gap', limited evaluation evidence has informed evidence-based policy and practice. Indigenous leaders have called for evaluation stakeholders to align their practices with Indigenous approaches. Methods: This study aimed to strengthen culturally safe evaluation practice in Indigenous settings by engaging evaluation stakeholders, in both countries, in a participatory concept mapping study. Concept maps for each country were generated from multi-dimensional scaling and hierarchical cluster analysis. Results: The 12-cluster Australia map identifies four cluster regions: An Evaluation Approach that Honours Community; Respect and Reciprocity; Core Heart of the Evaluation; and Cultural Integrity of the Evaluation. The 11-cluster New Zealand map identifies four cluster regions: Authentic Evaluation Practice; Building Māori Evaluation Expertise; Integrity in Māori Evaluation; and Putting Community First. Both maps highlight the importance of cultural integrity in evaluation. Differences include the distinctiveness of the 'Respecting Language Protocols' concept in the Australia map in contrast to language being embedded within the cluster of 'Knowing Yourself as an Evaluator in a Māori Evaluation Context' in the New Zealand map. Participant ratings highlight the importance of all clusters with some relatively more difficult to achieve, in practice. Notably, the 'Funding Responsive to Community Needs and Priorities' and 'Translating Evaluation Findings to Benefit Community' clusters were rated the least achievable, in Australia. The 'Conduct of the Evaluation' and the 'Prioritising Māori Interests' clusters were rated as least achievable in New Zealand. In both countries, clusters of strategies related to commissioning were deemed least achievable. Conclusions: The results suggest that the commissioning of evaluation is crucial as it sets the stage for whether evaluations: reflect Indigenous interests, are planned in ways that align with Indigenous ways of working and are translated to benefit Indigenous communities Identified strategies align with health promotion principles and relational accountability values of Indigenous approaches to research. These findings may be relevant to the commissioning and conduct of Indigenous health program evaluations in developed nations.