Lanthanide tags offer the opportunity to retrieve long-range distance information from NMR experiments that can be used to guide protein docking. To determine whether sufficient restraints can be retrieved for proteins with low solubility and availability, Ln tags were applied in the study of the 65 kDa membrane-associated protein complex formed by the electron carrier adrenodoxin and its electron donor, adrenodoxin reductase. The reductase is only monomeric at low concentration, and the paramagnetic iron-sulfur cluster of adrenodoxin broadens many of the resonances of nuclei in the interface. Guided by the paramagnetic restraints obtained using two Ln-tag attachment sites, protein docking yields a cluster of solutions with an rmsd of 3.2 A. The mean structure is close to the crystal structure of the cross-linked complex, with an rmsd of 4.0 A. It is concluded that with the application of Ln tags paramagnetic NMR restraints for structure determination can be retrieved even for difficult, low-concentration protein complexes.