The development of 15N, 13C, 2H multidimensional NMR spectroscopy has facilitated the assignment of backbone and side chain resonances of proteins and protein complexes with molecular masses of over 30 kDa. The success of these methods has been achieved through the production of highly deuterated proteins; replacing carbon-bound protons with deuterons significantly improves the sensitivity of many of the experiments used in chemical shift assignment. Unfortunately, uniform deuteration also radically depletes the number of interproton distance restraints available for structure determination, degrading the quality of the resulting structures. Here we describe an approach for improving the precision and accuracy of global folds determined from highly deuterated proteins through the use of deuterated, selectively methyl-protonated samples. This labeling profile maintains the efficiency of triple-resonance NMR experiments while retaining a sufficient number of protons at locations where they can be used to establish NOE-based contacts between different elements of secondary structure. We evaluate how this deuteration scheme affects the sensitivity and resolution of experiments used to assign 15N, 13C, and 1H chemical shifts and interproton NOEs. This approach is tested experimentally on a 14 kDa SH2/phosphopeptide complex, and a global protein fold is obtained from a set of methyl-methyl, methyl-NH, and NH-NH distance restraints. We demonstrate that the inclusion of methyl-NH and methyl-methyl distance restraints greatly improves the precision and accuracy of structures relative to those generated with only NH-NH distance restraints. Finally, we examine the general applicability of this approach by determining the structures of several proteins with molecular masses of up to 40 kDa from simulated distance and dihedral angle restraint tables.