The temperature of mantle plumes may vary on geologic time scales, from a few million years to tens of millions of years. In special circumstances such as near Iceland in the North Atlantic, where the plume underlies an oceanic spreading center, temporal variations in the oceanic crustal thickness provide a sensitive proxy for the mantle temperature if, as is likely, the crustal thickness is controlled primarily by passive decompression of mantle rising beneath the spreading center. We show from both seismic reflection imaging and wide-angle ocean bottom seismometer data from the Norwegian Sea that the temperature of the Iceland mantle plume decreased by ∼50 °C over the first 5 m.y. following continental breakup and then oscillated by ∼25 °C over an ∼3 m.y. period. Similar temperature variations on a 3–6 m.y. time scale, creating strong lineations in the gravity field, are inferred from the regional North Atlantic. They occur both in the period immediately following breakup and at the present-day Reykjanes Ridge south of Iceland, where they create V-shaped ridges as the mantle thermal anomalies propagate away from the center of the plume beneath Iceland. We propose that mantle plume temperature variations of ∼25 °C have occurred in the Iceland plume with a similar amplitude and frequency since at least 49 Ma, and are likely to be a feature of all mantle plumes.