This paper defines Australia's area of primary strategic interest, noting that this security in this region is very much concerned with maritime issues and capabilities; the waterways through the region are strategically important for both merchant and naval vessels, and coastal and offshore resources provide a principal means of livelihood in many countries of the region. It assesses the regional security environment, which is characterised by rapid change and increasing complexity and uncertainty, as security concerns broaden to include economic and environmental issues and more actors (with an improved range of capabilities) participate. It lists the reasons why greater regional cooperation is needed to manage this increasingly complex security environment, and advocates the construction of 'building blocks' - a multiplicity of subregional arrangements - towards enhanced security cooperation. The Timor Gap Treaty is examined as such a building block before suggesting two maritime confidence and security building measures - a regional maritime surveillance and safety regime, a a regional avoidance of incidents a sea regime.