The shared history and lived reality which exists between dogs and Indigenous peoples is one of entanglement at the physical, social, emotional, ecological, and cultural levels. While both species have been impacted by the losses and harms rooted in colonial events, genocidal practices reverberate into many lived realities, resulting in psycho-spiritual suffering among humans and non-humans, and the separation of nature and culture and predominant anthropocentrism which fuels unsustainable realities on the planet. Using an Indigenous participatory method combined with ethnographic analysis, this paper examines traditional relationships with dogs among various Indigenous communities, while identifying the distinct challenges and opportunities that dogs present for deconstructing anthropocentric structures. The wholistic health of dogs, humans and the broader interrelated realities are foundational for the decolonization of social and ecological realities, while contributing to true reconciliation between Indigenous and non-Indigenous bodies. The findings in this paper advocate for policy changes at health, educational, environmental and Indigenous levels, which acknowledge the non-human world and the human relationship with it, while highlighting the benefits of employing interdisciplinary methods in such pursuits. These relationships are biological, ecological, spiritual and cultural, with all non-humans holding vital roles within their environments and between human communities. The individuals which exist in non-human form, particularly among animals, comprise of sentience, autonomy and their own cognitive experience.