We present a method that significantly enhances the robustness of (automated) NMR structure determination by allowing the NOE data corresponding to unassigned NMR resonances to be used directly in the calculations. The unassigned resonances are represented by additional atoms or groups of atoms that have no interaction with the regular protein atoms except through distance restraints. These so-called "proxy" residues can be used to generate NOE-based distance restraints in a similar fashion as for the assigned part of the protein. If sufficient NOE information is available, the restraints are expected to place the proxies at positions close to the correct atoms for the unassigned resonance, which can facilitate subsequent assignment. Convergence can be further improved by supplying additional information about the possible identities of the unassigned resonances. We have implemented this approach in the widely used automated assignment and structure calculation protocols ARIA and CANDID. We find that it significantly increases the robustness of structure calculations with regard to missing assignments and yields structures of higher quality. Our approach is still able to find correctly folded structures with up to 30% randomly missing resonance assignments, and even when only backbone and beta resonances are present! This should be of significant value to NMR-based structural proteomics initiatives.