The structural and dynamical properties of OCS molecules solvated in Helium clusters are studied using reptation quantum Monte Carlo, for cluster sizes n=3-20 He atoms. Computer simulations allow us to establish a relation between the rotational spectrum of the solvated molecule and the structure of the He solvent, and of both with the onset of superfluidity. Our results agree with a recent spectroscopic study of this system, and provide a more complex and detailed microscopic picture of this system than inferred from experiments.