The olive grove is a globally recognized symbol of the Mediterranean landscape, yet its origins, ecology, and linkage to different cultures remain inadequately understood, especially in the Central and Western Mediterranean. To fill this gap, we provide new insights into the early exploitation of olive trees in Eastern Sicily (Italy) since the Early-Middle Bronze Age (18th cen. BCE, 3700 BP), through the integration of novel high-resolution palynological analyses of lake sediments at Pantano Grande (a.k.a. Lago di Ganzirri), paleoclimate proxies, and descriptions of socio-cultural changes from historical and archaeological sources. The study site is located along the Messina Strait: a trade and transit route used by seafarers to enter the Tyrrhenian Sea from the Eastern Mediterranean since prehistory. Vegetation changes, including the propagation of olive trees and other forms of land-use or rewilding, are found to be coincident with changing socio-cultural patterns over the last 3700 years. Our results suggest anthropogenic propagation of olive trees coinciding with three cultural stages: (i) Early-Middle Bronze Age (Castelluccio and Thapsos cultures); (ii) Roman times; (iii) Late Modern times (Kingdom of Sicily). This paper establishes an earlier date than previously recognized for the beginning of landscape transformations driven by olive tree exploitation in Italy, representing the second oldest evidence in the Central Mediterranean. We hypothesize that cultural exchanges between Sicily and the Aegean in the Early-Middle Bronze Age have promoted the use of wild olive trees in the Messina area. At that time, olive trees could have been used for various purposes, including fruit production, but also wood and forage for animals. The development of olive groves followed a gradual, multi-stage process in the Central Mediterranean, with large-scale cultivation appearing only in modern times. Although human impacts have contributed to the decline and local extinction of wild olive tree populations, it has also ensured the success of selected genotypes, enabling their adaptation to a wider range of environmental conditions.