We demonstrate the feasibility of elucidating the bound ("closed") conformation of a periplasmic binding protein, the glutamine-binding protein (GlnBP), in solution, using paramagnetic relaxation enhancements (PREs) arising from a single paramagnetic group. GlnBP consists of two globular domains connected by a hinge. Using the ligand-free ("open") conformation as a starting point, conjoined rigid-body/torsion-angle simulated annealing calculations were performed using backbone H-1(N)-PREs as a major source of distance information. Paramagnetic probe flexibility was accounted for via a multiple-conformer representation. A conventional approach where the entire PRE data set is enforced at once during simulated annealing yielded poor results due to inappropriate conformational sampling of the probe. On the other hand, significant improvements in coordinate accuracy were obtained by estimating the probe sampling space prior to structure calculation. Such sampling is achieved by refining the ensemble of probe conformers with intradomain PRIES only, keeping the protein backbone fixed in the open form. Subsequently, while constraining the probe to the previously found conformations, the domains are allowed to move relative to each other under the influence of the non-intradomain PREs, giving the hinge region torsional degrees of freedom. Thus, by partitioning the protocol into "probe sampling" and "backbone sampling" stages, structures significantly closer to the X-ray structure of ligand-bound GlnBP were obtained.