We present new trace element and isotopic data on a selection of least evolved lavas in Iceland. Pb isotopic compositions are variable: 206Pb/204Pb ranges from 18.05 in picrites to 19.15 in alkali basalts. Large excesses of Sr and Pb and a deficiency of Hf and Zr relative to rare earth elements are characteristic of the picritic lavas (Ce/Pb ≈ 10, Sr/Nd ≈ 35, and Sm/Hf ≈ 1.75), whereas more normal ratios are observed in the alkali basalts (Ce/Pb ≈ 40, Sr/Nd ≈ 10, and Sm/Hf ≈ 1.4). These variations are correlated to systematic changes in Sr, Nd, and Pb isotopic compositions. Using these new data, the relationship between the Iceland plume and the Mid-Atlantic Ridge can be reexamined. The 87Sr/86Sr versus 206Pb/204Pb relationship demonstrates clearly that all isotopic variations in Iceland have their origin in the plume source. In addition, the composition of both Reykjanes and Kolbeinsey Ridges results from contamination of the depleted mantle by the Iceland plume. Trace element and isotopic heterogeneities within Iceland are related to rock type and not to location in the island. This is contrary to what would be expected if a uniform plume mixed with surrounding mid-ocean ridge basalt (MORB), in which case the geochemical values would be more MORB-like at the perimeter. Instead, it suggests that the Iceland plume itself was highly heterogeneous. We propose that the source of the Iceland plume was old recycled oceanic crust that was stored in the mantle for a long time (potentially since the end of the Archean). Melting of the basaltic portion of this crust led to the formation of the alkali basalts, and melting of the clinopyroxene-plagioclase gabbroic portion of the same oceanic crust yielded the picritic basalts. In both cases, melting of the harzburgitic portion of the recycled lithosphere provided the necessary Mg and Ni. The tholeiites represent mixtures from the two sources. Iceland is therefore, together with Hawaii, a clear example of melting of a complete section of recycled oceanic lithosphere.