When conversations about Aboriginal student educational success emerge, they are usually focussed on the high levels of underachievement and disengagement. School leadership is seen as critical to contributing to student outcomes. For Aboriginal students, creating inclusive learning environments that support culture and identity, and building trusting relationships with families and community members are also critical goals. As part of the Aboriginal Voices project, this paper uses Decolonising Race Theory (Moodie, 2018) to analyse interviews with four Principals in urban, regional, and rural locations to understand their perceptions and experiences of leading Aboriginal education in schools. From the interviews, three key themes emerged: leading culture, identity and school-community relationships, leading curriculum, pedagogy and teacher development, and leading student participation and achievement. Decolonising Race Theory (Moodie, 2018) is applied as an analytical tool to view these themes through a critical Indigenous lens to understand the Principals' discourses around Aboriginal student experiences at school and their role in improving outcomes. This revealed contradictory positionings within and between Principal comments, from blaming students and their families for their underachievement, to implementing cultural programmes to build confidence to become self-determining adults. This data provides new ways of thinking through discourses about Aboriginal students and their families, communities, schools, teachers and Principals, and challenges some of the 'regimes of truth' that position these groups in particular ways.