This article describes our experience of conducting a 5-year, culturally responsive evaluation of a federal program with Indigenous communities. It describes how we adapted tenets from "participatory evaluation models" to ensure cultural relevance and empowerment. We provide recommendations for evaluators engaged in similar efforts. The evaluation included "stakeholder engagement" through a Steering Committee and an Evaluation Working Group in designing and implementing the evaluation. That engagement facilitated "attention to Indigenous cultural values" in developing a program logic model and medicine wheel and in gathering local perspectives through storytelling to facilitate understanding of community traditions. Our ongoing assessment of program grantees' needs shaped our approach to "evaluation capacity building" and development of a diverse array of experiential learning opportunities and user-friendly tools and resources. We present practical strategies from lessons learned during the evaluation design and implementation phases of our project that might be useful for other evaluators.