Ever since diplomatic relations were normalised by the Whitlam government in 1972, maintaining a constructive and productive relationship with China has been a challenge for successive Australian governments. The period under study here – from 1996 to 2000 – is further evidence that Australia’s relationship with China is shaping up as the toughest foreign policy task in the twenty-first century. There are three reasons for this. First is the growing power asymmetry between the two countries and the fact that while Australia is essentially a status quo power, China is non-status quo, dissatisfied with the current distribution of power in the region. Second, the nature of Australia’s relations with China has now come to depend increasingly on Beijing’s self-perception of its future role and interests in the region. Last but not least, the wide divergence in the two countries’ philosophical approaches to governance, political culture, and values introduces an element of uncertainty and unpredictability in the bilateral relationship.