Assessing the onset and extent of Northern Hemisphere glaciation is required to understand Cenozoic climate change and its impact on topography. While the onset of accelerated Cenozoic erosion is generally associated with the Quaternary at mid-latitudes, some high-latitude passive margins may have undergone earlier glaciation starting at 38–30 Ma or even 45 Ma. Here we document a rapid phase of exhumation in the East Greenland margin between 68°N and 76°N starting at 30 ± 5 Ma. The timing is coincident with the dramatic worldwide fall of surface temperature at the Eocene-Oligocene transition. Our inference is based on apatite fission track and apatite helium data. We suggest that a transition from an Eocene fluvial to an Oligocene glacial-dominated landscape triggered a period of enhanced erosion. This study provides the first onshore potential evidence of the onset of continental ice in East Greenland margin at the Eocene-Oligocene transition (ca. 34 Ma), contemporaneously with the onset of Antarctica glaciation and erosion. Our interpretation is consistent with that based on the oldest ice-rafted debris found in the sedimentary records offshore East Greenland and implies that East Greenland exhibits the oldest onshore record of Cenozoic glacial erosion on Earth.