In 1890, the Australian colonial politician, Henry Parkes, referred to the 'crimson thread of kinship' which he believed bound Australians to the United Kingdom. Within an increasingly multicultural Australia, situated within the Asia-Pacific region, such ties to the United Kingdom might be thought an anachronistic aspect of Australia's past. Yet in the 1990s and 2000s, two Australian Prime Ministers, who shared sixteen years of office between them, placed Australia's relationship to the United Kingdom at the centre of their respective political agendas, and at the core of their engagement with each other. This article seeks to investigate why this aspect of Australia's past took on such a contemporary importance during the Prime Ministerships of Paul Keating and John Howard, and focuses on the discursive strategies each Prime Minister adopted to render the 'crimson thread' such a salient feature of the Australian political landscape.