This paper describes the application of optically pumped xenon NMR to probe the surface of semiconductor nanocrystals by physisorption at 123 K. These experiments were made possible by using highly spin ordered Xe-129, prepared by optical pumping and spin exchange of a rubidium xenon gas mixture, to increase the NMR signal strength. CdS nanocrystals were prepared by regulated growth in inverse micelles and precipitated by surface derivatization with thiophenol. Nanocrystals of 11.8, 12.8, and 23 Angstrom radii with 26%, 63%, and 57% thiophenol surface coverage, respectively, were characterized. Within this sample parameter space, the Xe-129 spectra, recorded at varying xenon coverages, depended strongly on thiophenol surface coverage but were not sensitive to the crystallite size. In addition, the nanocrystals with low thiophenol coverage yielded a xenon line shape consisting of two components, interpreted as xenon signals arising from distinct surface domains. These domains are presumably formed by the aggregation of thiophenol molecules on the nanocrystal surface when the thiophenol coverage is incomplete, a model which is consistent with existing X-ray photoelectron spectroscopy and liquid state H-1 NMR data.