Past fish provenance, exploitation and trade patterns were studied by analyzing phosphate oxygen isotope compositions (δ18OPO4) of gilthead seabream (Sparus aurata) tooth enameloid from archaeological sites across the southern Levant, spanning the entire Holocene. We report the earliest evidence for extensive fish exploitation from the hypersaline Bardawil lagoon on Egypt's northern Sinai coast, as indicated by distinctively high δ18OPO4 values, which became abundant in the southern Levant, both along the coast and further inland, at least from the Late Bronze Age (3,550-3,200 BP). A period of global, postglacial sea-level stabilization triggered the formation of the Bardawil lagoon, which was intensively exploited and supported a widespread fish trade. This represents the earliest roots of marine proto-aquaculture in Late Holocene coastal domains of the Mediterranean. We demonstrate the potential of large-scale δ18OPO4 analysis of fish teeth to reveal cultural phenomena in antiquity, providing unprecedented insights into past trade patterns.