This paper looks to the geographies of Australia’s northern borderlands to theorise borders as relational spaces through which identities are (re)created and performed. Dominant Australian perspectives on borders are influenced by a legacy of exclusion and fear including the concept of terra nullius. This fear has been reinforced through the Australian government’s response to asylum seekers in the form of the Pacific Solution. Alternative perspectives of borderlands as sites of coexistence, complexity and situated engagement challenge this dominant conception of borderlands. Seeing borderlands as relational spaces allows for an understanding of borders as having the potential for inclusion or exclusion, as flexible and rigid, as based on fear or respect, depending on the relationships of power at work. We draw upon post-colonial and indigenous studies literature with a case study of the Tiwi Islands to argue that interconnected issues of power and identity are central to reimagining borders and borderlands.