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.