Indigenous communities increasingly assert their right to self-determination by requiring that participatory research approaches be used, valuing and prioritizing Indigenous knowledges, for the purpose of improving Indigenous health. While frameworks that focus on Indigenous knowledges are being developed, these must be adapted or developed by Indigenous communities because their knowledge is specific to place and inherent to their lived experience. No community-based participatory research (CBPR) framework for health research has been developed with the Labrador Innu. In addition, while the literature emphasizes the importance of relationship in research with Indigenous communities, the process of establishing relationships is underspecified. Within this context, we describe our experience in developing a CBPR framework for health research in a study that is community-initiated and fitting within Innu self-determination. We highlight the importance of paying attention to the theoretical roots of CBPR, arguing that this helps researchers focus on the centrality of Indigenous knowledges (in this case, Innu knowledge). This requires that non-Indigenous researchers question assumptions of universality regarding their own knowledge and see all knowledges as equitable. Such posture of humility allows non-Indigenous researchers to enter relational spaces that join researchers and Indigenous communities. Within these spaces, a true collaborative approach is enabled and Indigenous knowledges are uncovered and become foundational in the inquiry process. We illustrate these ideas by describing a model for opening relational spaces that include Indigenous and non-Indigenous researchers. We then present a framework that uses the metaphor of canoeing together to capture our CBPR approach for use in Innu health research. We outline the behaviors of non-Indigenous researchers to build and solidify relationships with Indigenous community researchers over time. This article is useful for non-Indigenous researchers interested in relational approaches to research with Indigenous communities, and for Indigenous leaders and researchers who seek community solutions through research.