A major challenge for the structure determination of integral membrane proteins by solution NMR spectroscopy is the limited number of NOE restraints in these systems stemming from extensive deuteration. Paramagnetic relaxation enhancement (PRE) by means of nitroxide spin-labels can provide valuable long-range distance information but, in practice, has limits in its application to membrane proteins because spin-labels are often incompletely reduced in highly apolar environments. Using the integral membrane protein OmpA as a model system, we introduce a method of parallel spin-labeling with paramagnetic and diamagnetic labels and show that distances in the range 15-24 Angstroms can be readily determined. The protein was labeled at 11 water-exposed and lipid-covered sites, and 320 PRE distance restraints were measured. The addition of these restraints resulted in significant improvement of the calculated backbone structure of OmpA. Structures of reasonable quality can even be calculated with PRE distance restraints only, i.e., in the absence of NOE distance restraints.