We present high resolution spectra of He(N)-OCS clusters with N up to 39 in the microwave and 72 in the infrared regions, observed with apparatus-limited line widths of about 15 kHz and 0.001 cm(-1), respectively. The derived rotational constant, B (proportional to the inverse moment of inertia), passes through a minimum at N=9, then rises due to onset of superfluid effects, and exhibits broad oscillations with maxima at N=24, 47 and minima at 36, 62. We interpret these unexpected oscillations as a manifestation of the aufbau of a nonclassical helium solvation shell structure. These results bridge an important part of the gap between individual molecules and bulk matter with atom by atom resolution, providing new insight into microscopic superfluidity and a critical challenge for theory.