Stable isotope and elemental analyses of the Atlantic cod (Gadus morhua) and harp seal (Phoca groenlandica) bone component of the marine food that dominated the Younger Stone Age (c. 6.1–3.5 ka BP) diet in Varanger, Arctic northern Norway, indicate, at times, climate change induced highly elevated levels of the heavy metals cadmium (Cd) and lead (Pb), and elevated levels of mercury (Hg). On average, the levels of cadmium and lead contamination in cod were up to 22 and 3–4 times, respectively, higher than today's recommended limits in soft tissue. The corresponding figures for seal were 15 and 3–4 times, respectively. The levels of Hg were generally below today's recommended limit in soft tissue, but still of considerable magnitude, almost similar to the measured values in modern fish in the Arctic. This shows that marine food in the Younger Stone Age was unhealthy, if not unsafe. We discuss this unexpected knock-on effect in terms of sea surface temperatures and sea level change. The elevated values may have been detrimental for humans, if not for society; a balancing factor may have been a larger component of terrestrial resources than previously assumed. Concomitantly, this contribution to the paleo base-line record of toxicity may lead to predictions for seafood contamination in the future.