Indigenous communities in Canada have struggled with systemic inequities that have affected education outcomes of their children. In collaboration with a Stoney Nakoda community in Western Canada, a university research team, composed of Indigenous and non-Indigenous members, offered an instruction program designed to use storytelling as a gateway to early literacy development. Indigenous researchers and collaborators guided program adaptation to increase its cultural relevance, and non-Indigenous researchers drew upon developmental research to tailor scaffolded instruction that supported increased story-structure complexity. A total of 100 children aged 5 to 7 years participated in an eight-month storytelling program, which included pre- and post-instruction assessments of storytelling and recall. After instruction, participants generated more complex, detailed stories that contained more references to their culture compared to same-age peers. They also more accurately recalled the gist of stories they were read. This study demonstrates the importance of making curricula relevant to Indigenous children by including content that is culturally relevant and developmentally appropriate.