In 1888 the Australian colonies came together to implement uniform laws to restrict Chinese immigration, leading eventually to the introduction of the Immigration Restriction Act after Federation in 1901. Alongside immigration restriction, after 1888 four Australian colonies also prohibited Chinese naturalisation, by law in New South Wales and by policy in Victoria, South Australia and Western Australia. The federal Naturalisation Act of 1903 similarly prohibited Chinese naturalisation. Before these restrictions were introduced, however, thousands of Chinese men in Australia became British subjects through naturalisation, nearly 1000 in New South Wales alone. In this paper I consider the legacies of colonial naturalisation in the lives of Chinese migrants and their families in the 1890s and after Federation, particularly concerning mobility and residency rights. I argue that it is through the stories of individual lives, revealed in the press and in government case files, that we can best understand the ways that naturalised Chinese Australians and their children contested discrimination and asserted their rights as citizens.