Eclogites and gneisses from the Yuka and Xitieshan areas in the North Qaidam orogen, NE Tibet, experienced ultrahigh-pressure (UHP) metamorphism in the early Paleozoic, when the Qaidam block subducted northwards beneath the Qilian block. U-Pb ages, trace-element patterns and Hf-isotope compositions of zircon in the two rock types were used to trace the isotopic and elemental changes within zircon during continental subduction and exhumation, and to examine the links between the igneous protolith and tectonic behavior of the subducting block. Zircon data suggest that the eclogites had igneous protoliths with ages of ca. 785±20Ma (2σ, MSWD=3.4, n=5), and most zircons metamorphically recrystallized during eclogitization at ca. 441±2Ma (2σ, MSWD=1.15, n=41); minor changes were caused by retrogression during ~417-409Ma. Trace elements of these zircons were incompletely reset in the prograde and retrograde processes; however, their Lu-Hf isotopic compositions retained the primary igneous 176Hf/177Hf ratios, reflecting a large extent of initial heterogeneity (εHf(t)=+14.0 to -19.5), even within single grains. Lu/Hf ratios decreased as a result of the eclogitization, and then increased again during retrogression. The behaviors of the U-Pb and Lu-Hf isotopic systems as well as the trace elements of the eclogitic zircons were decoupled during the early Paleozoic orogeny.Zircons from the gneisses mostly preserved their primary diverse signatures (εHf(t)=+15.8 to -17.9; crustal model ages=2.54-0.80Ga), but some ~440Ma metamorphic grains show lower trace-element concentrations than the Proterozoic zircons. U-Pb and Lu-Hf isotopic data in this study and from the literature reveal the existence of Neoarchean (ca. 2.8-2.5Ga) components in the Qaidam block as the initial protoliths of the gneisses, which were intruded by depleted-mantle (DM) magmas at ~2.1-2.0Ga and 1.1-0.8Ga. The igneous protoliths of the eclogites were emplaced into the protoliths of gneisses at ~850-750Ma, and are interpreted here as having formed by magmatic mixing between juvenile components from the DM and evolved material from the Archean Qaidam crust. This 1.1-0.8Ga magmatism has largely "rejuvenated" the Qaidam bock, at least its northern margin, and added more mafic material into its deep crust and upper mantle, as also indicated by geophysical observations. This lithosphere, and perhaps lower crust, of this continental block would become denser during subduction because of the extensive generation of garnet in the deep lithosphere, causing it to act as a "sinker." The intrinsically basic nature of the deep levels of the Qaidam block pre-determined its deep subduction into the mantle depths at ~440Ma, and then the less dense upper crust was detached from the deeper levels and exhumed later.