High-Fo olivine (Fo = Mg/(Mg+Fe) mol%) is an ideal proxy for establishing the compositions of primary melts and their mantle sources. This has been exploited in establishing lithological variations in the mantle source regions of oceanic basalts, including in Iceland. However, previous studies on Icelandic olivine lack spatial and temporal coverage. We present high-precision in-situ major, minor and trace element analyses of Fo-rich olivine from a suite of 53 primitive basalts erupted in the neovolcanic rift and flank zones of Iceland, as well as in older regions of Quaternary and Tertiary crust. Most of these samples have previously been analysed for 3He/4He, which ranges from 6.7 to 47.8 RA, the largest span reported for any oceanic island. By combining trace elemental variability with 3He/4He, we assess the extent of lithological variability in the Icelandic mantle plume. Trace-element ratios that are likely to preserve information about mantle source regions (e.g., Mn/Fe, Ni/(Mg/Fe), Ga/Sc, Zn/Fe and Mn/Zn) suggest a peridotitic mantle source in all rift-related volcanic regions, as well as in the off-rift flank zones of Öræfajökull and Snæfellsnes. However, a signal of a more pyroxenitic mantle lithology is clearly visible in olivine from the South Iceland Volcanic Zone, which represents the southward propagation of the Eastern Rift Zone, while olivine from Tertiary lavas suggests a mixed peridotite-pyroxenite source composition. We are able to identify four components present in the Icelandic mantle: a lithologically heterogeneous plume component with 3He/4He >MORB; a depleted MORB-like peridotite; an isotopically enriched MORB-like peridotite; and a peridotitic component with 3He/4He <MORB, sampled in the off-rift flank zone at Öræfajökull. The spatial distribution of these four components can be explained by a northward tilted mantle plume. This has previously been proposed by geophysical and geochemical studies of both Hawaii and Iceland suggesting that the plume geometry could be a contributing factor in controlling some of the spatial variation in source lithology beneath ocean islands.