Global climate change and its impact on public health exemplify the challenge of managing complexity and uncertainty in health research. The Canadian North is currently experiencing dramatic shifts in climate, resulting in environmental changes which impact Inuit livelihoods, cultural practices, and health. For researchers investigating potential climate change impacts on Inuit health, it has become clear that comprehensive and meaningful research outcomes depend on taking a systemic and transdisciplinary approach that engages local citizens in project design, data collection, and analysis. While it is increasingly recognised that using approaches that embrace complexity is a necessity in public health, mobilizing such approaches from theory into practice can be challenging. In 2009, the Rigolet Inuit Community Government in Rigolet, Nunatsiavut, Canada partnered with a transdisciplinary team of researchers, health practitioners, and community storytelling facilitators to create the Changing Climate, Changing Health, Changing Stories project, aimed at developing a multi-media participatory, community-run methodological strategy to gather locally appropriate and meaningful data to explore climate-health relationships. The goal of this profile paper is to describe how an EcoHealth approach guided by principles of transdisciplinarity, community participation, and social equity was used to plan and implement this climate-health research project. An overview of the project, including project development, research methods, project outcomes to date, and challenges encountered, is presented. Though introduced in this one case study, the processes, methods, and lessons learned are broadly applicable to researchers and communities interested in implementing EcoHealth approaches in community-based research.