A long history of tribal disenfranchisement through government policies has contributed to a lack of trust and participation by tribal communi­ties in nontribal organizations and initiatives. This article will discuss the process through which new partnerships were forged using a community-based participatory research (CBPR) approach among university researchers, local nontribal organiza­tions, and three Tribes in the Klamath River Basin of southern Oregon and northern California through a five-year federal food security grant. The partnership’s shared goal was to enhance tribal health and food security and food sovereignty in the Klamath River Basin by building a healthy, sus­tainable, and culturally relevant food system. We describe the context that gave rise to this collabo­rative partnership; share reflections on how project goals, objectives, and activities were co-created, adapted, and implemented; and highlight specific examples of research, education, and extension activities, informed by CBPR, that support the tribal goals of strengthening Indigenous food sovereignty. We also share lessons learned from navigating unforeseen challenges in ways that we hope can provide insight for scholars, cooperative extension advisors, nonprofit organizations, and government agencies seeking to build effective partnerships with tribes working toward food system change in Native American communities.