The East Asian winter monsoon (EAWM) significantly impacts living conditions in a large part of Asia, and therefore, it is important to understand its major driving mechanisms. Winter sea surface temperature (SSTW) and circulation in the southern Okinawa Trough are today both primarily controlled by the EAWM. Here we present a new SSTW reconstruction for the last millennium based on a diatom record from sediment core MD05-2908, from the continental slope of the southern Okinawa Trough off northeastern Taiwan. Our reconstruction indicates that SSTW varied between 14.1 and 19.6°C over the past 1,000 years. Changes in SSTW in the southern Okinawa Trough correspond closely to the index of warm winters based on historical documents from the East Asian monsoon domain. This implies that our SSTW record can be used to reconstruct EAWM variability during the last millennium. Comparisons with the reconstructed winter Arctic Oscillation (AO, developed from historical snow anomaly events in Eastern Asia) and Arctic sea ice cover reveal a significant positive correlation between the EAWM and AO during the time interval from 1000–1400 Common Era (C.E.), coinciding with reduced sea ice cover. However, there is no significant correlation with increased sea ice cover during the interval from 1400 to 1700 C.E. This suggests that the reduction in Arctic sea ice may periodically have played a role in strengthening the relationship between the EAWM and the AO during the last millennium and that the current and future reduction in Arctic sea ice may have significant consequences for the EAWM.