Geological observations that constrain the history of mantle convection are sparse despite its importance in determining vertical and horizontal plate motions, plate rheology, and magmatism. We use a suite of geological and geophysical observations from the northern North Sea to constrain evolution of the incipient Paleocene-Eocene Icelandic plume. Well data and a three-dimensional seismic survey are used to reconstruct a 58–55 Ma landscape now buried ∼1.5 km beneath the seabed in the Bressay region. Geochemical analyses of cuttings from wells that intersect the landscape indicate the presence of angiosperm debris. These observations, combined with presence of coarse clastic material, interpreted beach ridges, and a large dendritic drainage network, indicate that this landscape formed subaerially. Longitudinal profiles of palaeo-rivers were extracted and inverted for an uplift rate history, indicating three distinct phases of uplift and total cumulative uplift of ∼350 m. Dinoflagellate cysts in the surrounding marine stratigraphy indicate that this terrestrial landscape formed in <3 Ma and was rapidly drowned. This uplift history is similar to that of a slightly older buried landscape in the Faeroe-Shetland basin ∼400 km to the west. These records of vertical motion are consistent with pulses of anomalously hot asthenosphere spreading out from the incipient Icelandic plume. Using simple isostatic calculations we estimate that the maximum thermal anomaly beneath Bressay was 50–100◦C. Our observations suggest that a thermal anomaly departed the Icelandic plume around 57.4±2.2 Ma at the latest, and travelled with a velocity >∼150 km/Ma.