Climatic models simulate abrupt oscillations that are associated, in the North Atlantic, with Dansgaard-Oeschger and Heinrich events. However, the geographic extension of temperature anomalies is largely uncontrolled due to the scarcity of quantitative records of sufficient time resolution on the European continent. Here, we propose, based on a recently developed temperature proxy (TEX86), a reconstruction of millennial-scale temperature variations in a Black Sea sediment archive for the last 40,000 years. Prior to any paleoclimatological interpretations the effects of potential bias, such as seasonality and depth of maximum export production on temperature reconstructions, are considered for the Black Sea. Based on previous work, a tentative method for temperature corrections, taking into account varying terrigenous inputs, is further proposed. Reconstructed temperatures for Black Sea core MD042790 were remarkably stable during the last glacial. However, significant shifts toward lower temperatures of 2°C occurred during Heinrich events 2 and 3. The deglaciation displayed a temperature increase of 10°C consistent with neighboring European reconstructions. A Younger Dryas cooling of approximately 5–6°C was clearly expressed in the reconstruction. In notable contrast to observations from nearby archives, Heinrich events imprinted our glacial temperature record consistent with a strong reorganization of oceanic circulation and a large spreading of the temperature anomaly from the North Atlantic toward the southeast. Furthermore, in contrast to high-latitude records, our Black Sea record lacks the signatures of Dansgaard-Oeschger interstadials, suggesting a decreasing temperature gradient away from the North Atlantic.