The Eocene-Oligocene (E-O) boundary interval is considered to be one of the major transitions in Earth's climate, witnessing the first major expansion of the East Antarctic Ice Sheet. However, the extent of the associated climatic cooling, especially for high northern latitude continental landmasses, is poorly constrained. In this study we reconstruct the first mean annual air temperature (MAAT) for the Greenland landmass during the late Eocene and early Oligocene by applying a new proxy based on the distribution of branched tetraether lipids derived from soil bacteria preserved in a marine sediment core from the Greenland Basin. The temperature estimates are compared with a composite continental temperature record based on bio-climatic analysis of pollen assemblages. Both proxies reveal comparable late Eocene MAATs of ∼13–15 °C and a gradual long-term cooling of ∼3–5 °C starting near the E-O boundary. These data are in agreement with other MAAT reconstructions from northern midlatitude continents and suggest a general cooling of the Northern Hemisphere during the E-O transition.