The notion that Indigenous tourism can advance reconciliation contrasts with prevailing ‘tourism as industry’ discourses. Commodification processes treat tourists as consumers, rather than as visitors to a place, or visitors to the people of a place. How can Indigenous tourism deliver sustainable benefits to the hosts and communities that receive visitors? This study adopts critical Indigenous methodology with constructivist grounded theory, as we source and validate theoretical constructs of sustainability in Indigenous tourism with Aboriginal tourism operators themselves. Three practices emerge, namely hosting, connecting, and sharing. Through hosting, operators set the scene for culturally safe interactions. Through connecting, hosts and tourists recognise their shared humanity. Through sharing, local identities, cultures, and histories are brought to the surface. These three practices of hosting, connecting, and sharing arise from the agency, and thereby reinforce the agency, of Aboriginal tourism operators. In order for Indigenous tourism operators and communities to derive sustainable benefits from receiving visitors, such engagements must be founded on recognition and respect for Indigenous agency. These practices imply reciprocity and point to local understandings of reconciliation, not as an endpoint, but as a practice in the here and now. We argue that this represents a strengths-based model of Indigenous tourism.