This paper engages with Indigenous peoples' conceptualisations of borders, arguing that these unsettle dominant Eurocentric constructs of the border as terrestrial, linear, bound and defined through western legal frameworks. It does this by drawing on one aspect of the many storytelling experiences offered by members of the Indigenous-owned Yolngu tourism business Bawaka Cultural Experiences in northern Australia. We argue that stories told to visitors about multiple and diverse connections between Yolngu and Makassan people from Sulawesi, Indonesia, are intentional constructions which challenge dominant conceptions of Australia as an isolated island-nation. The stories redefine the border as a dynamic and active space and as a site of complex encounters. The border itself is continuously recreated through stories in ways that emphasise the continuity and richness of land and sea-scapes and are based on non-linear conceptions of time. The stories invite non-Indigenous people to engage with different kinds of realities that exist in the north and to re-imagine Australia's north as a place of crossings and connections.