The relative importance of paramagnetism-based constraints (i.e. pseudocontact shifts, residual dipolar couplings and nuclear relaxation enhancements) with respect to classical constraints in solution structure determinations of paramagnetic metalloproteins has been addressed. The protein selected for the study is a calcium binding protein, calbindin D9k, in which one of the two calcium ions is substituted with cerium(III). From 1823 NOEs, 191 dihedral angles, 15 hydrogen bonds, 769 pseudocontact shifts, 64 orientational constraints, 26 longitudinal relaxation rates, plus 969 pseudocontact shifts from other lanthanides, a final family with backbone r.m.s.d. from the average of 0.25 A was obtained. Then, several families of structures were generated either by removing subsets of paramagnetism-based constraints or by removing increasing numbers of NOEs. The results show the relative importance of the various paramagnetism-based constraints and their good complementarity with the diamagnetic ones. Although a resolved structure cannot be obtained with paramagnetism-based constraints only, it is shown that a reasonably well resolved backbone fold can be safely obtained by retaining as few as 29 randomly chosen long-range NOEs using the standard version of the program PSEUDYANA.