This paper presents results from a recently completed inquiry that investigated culturally relevant physical education for Aboriginal students. Employing a decolonizing research methodology (storywork), we engaged seven Mi'kmaw Elders and three Mi'kmaw community physical activity/education leaders in conversations about culturally relevant physical education. Attending to Halas, McCrae, and Carpenter's (2012) framework for culturally relevant physical education, we share our findings related to Mi'kmaw students and school communities. The results ought to be of notable interest to those who share an interest in culturally relevant pedagogy, physical education, and/or Aboriginal education.