Nuclear magnetic resonance spectroscopy (NMR) can provide a great deal of information about structure and dynamics of biomolecules. The quality of an NMR structure strongly depends on the number of experimental observables and on their accurate conversion into geometric restraints. When distance restraints are derived from nuclear Overhauser effect spectroscopy (NOESY), stereo-specific assignments of prochiral atoms can contribute significantly to the accuracy of NMR structures of proteins and nucleic acids. Here we introduce a series of NOESY-based pulse sequences that can assist in the assignment of chiral CHD methylene protons in random fractionally deuterated proteins. Partial deuteration suppresses spin-diffusion between the two protons of CH2 groups that normally impedes the distinction of cross-relaxation networks for these two protons in NOESY spectra. Three and four-dimensional spectra allow one to distinguish cross-relaxation pathways involving either of the two methylene protons so that one can obtain stereospecific assignments. In addition, the analysis provides a large number of stereospecific distance restraints. Non-uniform sampling was used to ensure optimal signal resolution in 4D spectra and reduce ambiguities of the assignments. Automatic assignment procedures were modified for efficient and accurate stereospecific assignments during automated structure calculations based on 3D spectra. The protocol was applied to calcium-loaded calbindin D-9k. A large number of stereospecific assignments lead to a significant improvement of the accuracy of the structure.