There is considerable current concern about sea-level rise in the Southeast Asian region. Many countries are low-lying and only a small increment would see large land areas under water, which in turn has implications for population relocation. However, the process of regional sea-level rise is hardly new. At the last glacial maximum, 17kya, the sea was some 120m below present levels and many areas which are currently islands were previously joined to the mainland. The gradual rise in sea-level has had important implications for population distribution. We assume that prior to 17kya there was a continuous Austromelanesian population distributed from New Guinea to mainland Southeast Asia. This is currently represented only by the remaining Andamanese, the Orang Asli, and the Philippines negritos, apart from the main Papuan populations. Although we assume these populations were connected linguistically, no convincing argument for this can now be made based on the remaining fragmentary records. The original colonisation of the region, which included Denisovans, must have been largely on foot, although watercraft were later necessary for the crossing to Australia and to reach the Solomons. The hypothesis is that rising sea-levels stimulated improved maritime capacity, expanded pelagic fisheries, and isolated forager groups on individual islands, losing cultural connectivity. However, the rise of the obsidian trade ca. 8000 BP promoted exchange and trader. It is argued that this may be linked to a migration of mainland mongoloid populations which eliminated the original inhabitants on some islands, such as Nias. Today the region is dominated by Austronesian speakers, who have culturally and genetically overwhelmed local populations on many islands, fragmenting the isolated groups which persisted. However, part of the logic of their success was adopting and adapting the maritime skills and knowledge of routes which had developed during the earlier Holocene.