The Innu of nitassinan, a territory which includes most of Québec and Labrador, have lived in this immense peninsula for 9000 years. This is testified to by oral histories within contemporary generational memory, Innu atanukana (parables containing collective memories of the deep past and interactions with both vanished pleistocene megafauna and supernatural beings) and archaeology. Despite drastic changes to Innu life-ways following government sponsored sedentarization and compulsory Western schooling, there remain tangible links between Innu people, their ancestors, and other-than-human beings – such as the guardian deities of the animals and other supernatural beings in nutshimit (the country). Such connections suggest that components of a relational ontology are woven into Innu life-ways, where both human and other-than-human beings are imbued with spirit, and their interactions are governed by protocols of proper behaviour and respect. There is also evidence to suggest metaphysical continuity between Innu and certain animals in nutshimit; the Kauatikamapeu atanukan (the boy who married a caribou), for example, exemplifies this as well as caribou-Innu reciprocity. We argue that this relationality forms part of the magical realism of the Innu world, which in itself resists binary categorization as secular or sacred. Otherwise prosaic chores, such as cleaning, processing and disposing of animal remains, thus acquire and are invested with spiritual power tied to the daily maintenance of human and other-than-human reciprocal relationships in nutshimit. We offer two archaeological cases which demonstrate that approaching the archaeological record from this stance can provide a fresh interpretive lens to the study of Innu history and the deep past of nitassinan.