The rock magnetic and paleomagnetic results from the Upper Paleozoic sedimentary sequences composing the isles of the Novaya Zemlya Archipelago are presented. The recorded temperature dependences of the magnetic susceptibility, the magnetic hysteresis parameters, and the results of the first-order reversal curve (FORC) measurements suggest the presence of single-domain or pseudo-single-domain magnetite and hematite grains in the rocks. The Upper Paleozoic deposits overall are promising for unraveling the tectonic evolution of the Barents–Kara region. Together with the rock magnetic data, the positive fold and reversal tests testify to the primary origin of the indentified magnetization components. However, the interpretation of the paleomagnetic data should take into account the probable inclination shallowing. New substantiation is offered for the paleomagnetic poles for Early Devonian and Late Permian. For the first time, paleomagnetic constraints are obtained for the Late Carboniferous boundary. It is shown that the Early Cimmerian deformation stage within the Paikhoi–Novaya Zemlya region is associated with the sinistral strike slip displacement along the Baidaratskii suture during which the internal structure of the Southern Novaya Zemlya segment could undergo shear in addition to the nappe-thrust transformations. The Northern Novaya Zemlya segment, which is shifted northwest with respect to the Southern segment, was deformed in the thrusting mode with an overall clockwise rotation of this segment relative to the East European Craton.