Purpose: Using relationality and relational accountability as both a conceptual and methodological framework, this study explored the leadership practices of educational leaders in a community that a Wampanoag Tribe has called home for 12,000 plus years. It asked if and how leaders were exercising relationality and relational accountability in their engagement practices with Wampanoag and other Indigenous families and community members. Research Methods: Drawing from an exploratory case study that included 30 participants, 10 months of participant observation, 45 semi-structured conversations and interviews, and two talking circles, this article shares findings from observations, conversations, and interviews with six school and district leaders and five Indigenous parents and community leaders. Wilson's (2008) Intuitive logic and Braun's and Clarke's (2006) thematic analysis were used to identify the results that are presented in this article. Findings: Town and school history have been major barriers to building trusting and accountable relationships with Wampanoag families. Leaders nonetheless hoped to build relationships by creating opportunities for families to engage for what they called "community purposes" and through "open" and "reciprocal" communication. A newly formed Tribe-District Partnership held the most promise for building trusting and accountable relationships with Tribal members. Implications of Research and Practice: Relationality and relational accountability are powerful Indigenous protocols with the potential of disrupting colonial leadership practices that have perpetuated legacies of Indigenous erasure. Leadership towards relationality and relational accountability positions educational leaders to support Indigenous communities in their efforts to revitalize and sustain what legacies of colonization and colonial schools have disrupted.