The Middle East is one of the most water stressed regions in the world, receiving the majority of its hydrological input during the winter, in the form of highly variable and scattered precipitation. The persistence of wintertime anticyclonic conditions over the region can deflect storm tracks and result in extended spells of exceptionally hot weather, favoring prolonged droughts and posing a major threat to the already fragile hydrological equilibrium of the Middle East. Despite their potential impacts on water-security, winter warm spells (WWS's) have received far less attention than their summer counterparts, and the climatic drivers leading to WWS's onset are still largely unexplored. Here, we investigate their relationship with the internal modes of variability in the Atlantic Ocean, already known to influence winter circulation and extremes in Eurasia and Northern America. We show that the occurrence of WWS's is strongly correlated with Atlantic variability over decadal time scales. To explain this correlation, we propose a teleconnection mechanism linking Atlantic variability to WWS's via the propagation of Rossby waves from the North Atlantic pool, and the mediation of the Mediterranean circulation - thereby providing a basis to better predict future warming and aridification trends in the Middle East.