The Milos, Christiana-Santorini-Kolumbo (CSK) and Kos-Yali-Nisyros (KYN) volcanic complexes of the Aegean Volcanic Arc have repeatedly produced highly explosive eruptions from at least ∼360 ka into historic times and still show recent unrest. We present the marine tephra record from an array of 50, up to 7.4 m long, sediment cores along the arc collected in 2017 during RV Poseidon cruise POS513, which complements earlier work on distal to ultra-distal eastern Mediterranean sediment cores. A unique set of glass-shard trace element (LA-ICPMS) compositions complements our major element (EMP) data on 220 primary ash layers and 40 terrestrial samples to support geochemical fingerprinting for correlations with 19 known tephras from all three volcanic complexes and with the 39 ka Campanian Ignimbrite from the Campi Flegrei, Italy. The correlations include eleven eruptions from CSK (Kameni, Kolumbo 1650, Minoan, Cape Riva, Cape Tripiti, Upper Scoriae 1 and 2, Middle Pumice, Cape Thera, Lower Pumice, Cape Therma 3). We identify a previously unknown widespread tephra from a plinian eruption on Milos (Firiplaka Tephra). Near the KYN we correlate marine tephras with the Kos Plateau Tuff, the Yali 1 and Yali 2 tephras, and the Upper and Lower Pumice on Nisyros. Between these two major tephras, we found two tephras from Nisyros not yet observed on land. The four Nisyros tephras form a systematic trend toward more evolved magma compositions. In the companion paper we use the tephrostratigraphic framework established here to constrain new eruption ages and magnitudes as a contribution to volcanic hazard assessment.