The Mediterranean Sea is a mid-latitude marginal sea, particularly responsive to climate change as reported by recent studies. The Sicily Channel is a choke point separating the sea in two main basins, the Eastern Mediterranean Sea and the Western Mediterranean Sea. Here, we report and analyse a long-term record (1993-2016) of the thermohaline properties of the Intermediate Water that crosses the Sicily Channel, showing increasing temperature and salinity trends much stronger than those observed at intermediate depths in the global ocean. We investigate the causes of the observed trends and in particular determine the role of a changing climate over the Eastern Mediterranean, where the Intermediate Water is formed. The long-term Sicily record reveals how fast the response to climate change can be in a marginal sea like the Mediterranean Sea compared to the global ocean, and demonstrates the essential role of long time series in the ocean.