We demonstrate the feasibility of determining the global fold of a highly deuterated protein from unassigned experimental NMR nuclear Overhauser effect (NOE) data only. The method relies on the calculation of a spatial configuration of covalently unconnected protons-a "cloud"-directly from unassigned distance restraints derived from C-13-and N-15-edited NOESY spectra. Each proton in the cloud, labeled by its chemical shift and that of the directly bound C-13 or N-15, is subsequently mapped to specific atoms in the protein. This is achieved via graph-theoretical protocols that search for connectivities in graphs that encode the structural information within the cloud. The peptidyl H-N chain is traced by seeking for all possible routes and selecting the one that yields the minimal sum of sequential distances. Complete proton identification in the cloud is achieved by linking the side-chain protons to proximal main-chain (HS)-S-N via bipartite graph matching. The identified protons automatically yield the NOE assignments, which in turn are used for structure calculation with RosettaNMR, a protocol that incorporates structural bias derived from protein databases. The method, named Sparse-Constraint CLOUDS, was applied to experimental NOESY data on the 58-residue Z domain of staphylococcal protein A. The generated structures are of similar accuracy to those previously reported, which were derived via a conventional approach involving a larger NMR data set. Additional tests were performed on seven reported protein structures of various folds, using restraint lists simulated from the known atomic coordinates.