We present fully quantum calculations of the rotational energy levels and spectroscopic rotational constants of the linear OCS molecule in variable size clusters of 4He. The rotational constants of OCS are found to decrease monotonically from the gas phase value as the number of helium atoms increases to N=6, after which the average constant increases to saturation at the large droplet value by N=20. The minimum is shown to indicate a transition from a molecular complex to a quantum solvated molecule, with the former characterized by floppy but near rigid behavior, while the latter is characterized by nonzero permutation exchanges and a smaller extent of rigid coupling.