We present perturbational ab initio calculations of the nuclear-spin-dependent relativistic corrections to the nuclear magnetic resonance shielding tensors that constitute, together with the other relativistic terms reported by us earlier, the full leading-order perturbational set of results for the one-electron relativistic contributions to this observable, based on the (Breit-)Pauli Hamiltonian. These contributions are considered for the H(2)X (X = O,S,Se,Te,Po) and HX (X = F,Cl,Br,I,At) molecules, as well as the noble gas (Ne, Ar, Kr, Xe, Rn) atoms. The corrections are evaluated using the relativistic and magnetic operators as perturbations on an equal footing, calculated using analytical linear and quadratic response theory applied on top of a nonrelativistic reference state provided by self-consistent field calculations. The (1)H and heavy-atom nuclear magnetic shielding tensors are compared with four component, nearly basis-set-limit Dirac-Hartree-Fock calculations that include positronic excitations, as well as available literature data. Besides the easy interpretability of the different contributions in terms of familiar nonrelativistic concepts, the accuracy of the present perturbational scheme is striking for the isotropic part of the shielding tensor, for systems including elements up to Xe.