Human adaptations to marine resources were critical in the successful colonization of Island Southeast Asia (ISEA) and the Pacific since the Late Pleistocene. Fishing the dense biomass of ichthyofauna present in this maritime region required the cognitive capability to conceptualize fish ecology and develop methods and technologies to exploit these challenging underwater environments. This likely gave our species an edge over other hominin species in depauperate island landscapes. This paper reviews the limited number of archaeological sites in ISEA where fish bone assemblages and fishing gears have been recovered, incorporating new archaeological data from the site of Asitau Kuru (Jerimalai), Timor-Leste. Our findings indicate continuity in fishing behavior over several millennia with a near-shore exploitation of local marine habitats including trolling, line fishing and spearing. These data indicate the ecological plasticity of our species and the enduring fishing traditions passed on to generations through learned behavior.