A central challenge with participatory action research (PAR) pertains to discrepancies between principles and practice. What sounds simple in theory (e.g., establishing a respectful collaboration) is often much more complex in real community settings. The challenges, lessons learned, and successes of PAR were examined within the context of a large national research project that involved 8 First Nation communities and academics. To engage in the process of reflective examination, two methodological approaches were utilized: (1) a qualitative interview study with 19 project members about their experiences within the project, and (2) a secondary qualitative analysis of the author’s own experiences and observations (as recorded in research journals). This paper summarizes some of the barriers to conducting PAR with Indigenous communities (i.e., themes of distrust/personal safety concerns, community readiness, waning motivation, financial stress, power differences, and differing norms/expectations) , as well as some of the lessons that were learned about how to overcome these challenges and cultivate strong, healthy research relationships.