Trace elements (V, Cr, Mn, Fe, Co, Cu, Zn, As, Rb, Sr, Mo, Cd, Sb, Ba, Tl, Pb, Bi, Th and U) and Pb isotopic compositions from the EPICA (European Project for Ice Coring in Antarctica) Dome C ice core have been determined using inductively coupled plasma sector field mass spectrometry (ICP-SFMS) and thermal ionization mass spectrometry (TIMS), covering the period from ~533 kyr BP to ~800 kyr BP, respectively. Our data have enabled us to extend the previous EDC records of trace elements and Pb isotopes from the Holocene back to the Marine Isotopic Stage 20.2, ~800 kyr BP. We here discuss the EDC records of Ba, Rb, Mo, Sb, Cd, Tl, Bi and Pb isotopes. Crustal elements such as Ba and Rb show well defined variations in concentrations in relation to climatic conditions with lower values during the interglacial periods and much higher values during the coldest periods of the last eight climatic cycles. Volcanogenic Cd, Tl and Bi show a less pronounced relationship between concentrations and climatic conditions. The isotopic signatures of Pb suggest that changes in the provenance of dust reaching the East Antarctic Plateau from Potential Source Areas occurred during the interglacial periods before the MBE. Our data suggest that the main factors affecting deposition fluxes and sources of natural trace elements over Antarctica are most likely linked to a progressive coupling of the climates of Antarctica and lower latitudes over the past 800 kyr.