Despite long-standing sovereignty sensitivities, the Malacca and Singapore Straits have been the site of co-operative governance and regime building. Of note is the 2007 Co-operative Mechanism of the Straits of Malacca and Singapore, characterised as a milestone achievement in regional co-operation towards improved safety and security in the Straits. Yet, well before the Co-operative Mechanism were also earlier instances of co-operation dating to the 1970s – specifically between the Straits’ littoral states under a tripartite framework and Japanese actors through the Malacca Strait Council. In addition to providing a template for the Co-operative Mechanism, these arrangements offer alternative models of governance and regime building that challenge conventional characterisations of “regional governance” – what it looks like, as well as its driving actors. This article considers the significance of these early efforts, with attention to the ways that the region’s developmental context bears on the actors, structures and processes of governance in Southeast Asia. Not only does this historical process of co-operation give expression to alternative governing arrangements composed of mixed actors and obligations, but an unconventional governance agent – the Nippon Foundation – has played an especially defining role in bringing actors to the table and substantiating the co-operative process.