Nuclear magnetic resonance (NMR) structure calculations of the α-helical integral membrane proteins DsbB, GlpG, and halorhodopsin show that distance restraints from paramagnetic relaxation enhancement (PRE) can provide sufficient structural information to determine their structure with an accuracy of about 1.5 Å in the absence of other long-range conformational restraints. Our systematic study with simulated NMR data shows that about one spin label per transmembrane helix is necessary for obtaining enough PRE distance restraints to exclude wrong topologies, such as pseudo mirror images, if only limited other NMR restraints are available. Consequently, an experimentally realistic amount of PRE data enables α-helical membrane protein structure determinations that would not be feasible with the very limited amount of conventional NOESY data normally available for these systems. These findings are in line with our recent first de novo NMR structure determination of a heptahelical integral membrane protein, proteorhodopsin, that relied extensively on PRE data.