After the end of the Last Glacial Maximum, 450 km2 of former terrestrial and coastal landscape of the Maltese Islands was drowned by the ensuing sea level rise. In this study we use high resolution seafloor data (multibeam echosounder data, seismic reflection profiles, and Remotely Operated Vehicle imagery) and bottom samples to reconstruct ~ 300 km2 of this submerged Maltese paleolandscape. The observed paleolandscape is exceptionally well preserved and comprises former coastal landforms – (i) fault-related escarpments, (ii) paleoshore platforms and associated shorelines, (iii) paleoshoreline deposits, and (iv) mass movement deposits – and former terrestrial landforms – (v) river valleys, (vi) alluvial plains, (vii) karstified limestone plateaus, and (viii) sinkholes. These elements indicate that the paleolandscape has been primarily shaped by tectonic activity combined with fluvial, coastal, slope instability and karstic processes; these are the same processes the shaped the current terrestrial and coastal landscape. By correlating the identified landforms with the timing of known changes in sea level during the last glacial cycle, we infer that the alluvial plains and the shallowest limestone plateaus had up to 100 kyr to develop, whereas the paleoshoreline deposits are likely to have formed between 28 kyr and 14 kyr. The most prominent paleoshore platforms, shorelines and river valleys were generated between 60 kyr and 20 kyr. Fluvial erosion is likely to have been prevalent during periods of low sea level (Last Glacial Maximum and stadial conditions during MIS 3), whereas karst processes should have been more effective during warm and humid interstadial periods. Our results have implications for improving the characterization of past environments and climates, as well as providing a much needed background for prehistoric and geoarcheological research in the central Mediterranean region.