Sydney is an Indigenous place - Indigenous Country - infused with Indigenous stories and lore/Law. Yet as the original site of British colonisation in 1788, Sydney today is also a deeply-colonised place. Long-held narratives of Sydney as a colonial city have worked hard to erasure Indigenous peoples' presences and to silence Indigenous stories of this place (Rey and Harrison, 2018). In recent years, however, Indigenous-led tours on Country are emerging in the Greater Sydney region, whereby Indigenous guides share with visitors stories of place, history, culture, language and connection. We write together as Indigenous and non-Indigenous researchers, in conversation with four Indigenous tour operators in the Greater Sydney region to reflect on their experiences of conducting Indigenous tours in this Indigenous-yet-deeply-colonised place. We document the kinds of 'deep-colonising' (Rose, 1996) narratives and assumptions the operators encounter during their tours and within the tourism industry, and highlight how Indigenous tour operators facilitate many non-Indigenous peoples in taking their first steps towards meaningful interactions with Indigenous Sydney-siders. We conclude that Indigenous tour operators undertake incredibly complex, confronting and challenging emotional labours trying to change the pervasive and deep-colonising narratives and assumptions about Indigenous peoples in the Greater Sydney region. In a world where the histories of thousands of cities 'lie in dispossession and genocide of Indigenous peoples' (Porter, 2020: 15), we argue for further and careful analytical attention on Indigenous tourism encounters in Indigenous - yet deeply-colonised - places.