This article considers the regional order-building challenges that Australia presently confronts in the Indian Ocean region (IOR). The author argues that while regional stability within the IOR constitutes an increasingly important Australian security interest, policy makers will struggle to translate the order-building strategies they have previously pursued in East Asia into an Indian Ocean context. In East Asia, Australia has historically pursued a ‘dual track’ order-building strategy centred on its participation in a US-dominated ‘hub and spokes’ alliance system alongside multilateral regional engagement. The absence of an equivalent alliance system or an established tradition of multilateral security diplomacy conversely precludes an extension of this strategy into the IOR. Growing tensions between the USA and China and between China and India, meanwhile, further complicate IOR security dynamics, while underscoring the urgent need for a more coherent approach to regional order-building. With these challenges in mind, the author concludes by proposing a range of bilateral, minilateral and multilateral initiatives that Australia should pursue to stimulate the emergence of a more cooperative IOR security environment.