A multitude of educational programs attempt to facilitate young people's engagement with ideas and practices of active citizenship. For young Aboriginal and Torres Strait Islander or Indigenous people in Australia, such interventions are often subject to complex experiences of senses of belonging and non-belonging. This paper responds to calls from researchers to develop better understandings of young Indigenous people's own senses and practices of belonging and to better understand the ways in which these perspectives and practices are spatially influenced at the level of local communities, 'country' and cultural groupings, and within larger state, national or transnational settings. Their testimonies illustrate the tensions that young Indigenous people must navigate in a settler colony that has never truly recognised Indigenous sovereignty but show that sovereignty remains intact. Focus groups were conducted with 58 young Indigenous people in Melbourne and regional Victoria who were participating in an Indigenous youth leadership program designed to foster formal and informal active citizenship practices, and to nurture a strong, affirming sense of Indigenous identity. The testimonies of these participants provide valuable insights into educational sites as spaces in which young people experience a spectrum of weak to strong senses of belonging. They also provide insights into the possibilities of engaging the challenges faced by many young Indigenous people in educational settings, challenges that include race discordance and exclusion, deficit discourses and gaps and distances in educational practice. They highlight the need to recognise the aspirations of young Indigenous people and the capacities of colonial education systems to meet them, and the imperative to celebrate young Indigenous identities in meaningful, non-tokenistic ways.