The rotational dynamics of CO single molecules solvated in small He clusters (CO@He_N) has been studied using Reptation Quantum Monte Carlo for cluster sizes up to N=30. Our results are in good agreement with the roto-vibrational features of the infrared spectrum recently determined for this system, and provide a deep insight into the relation between the structure of the cluster and its dynamics. Simulations for large N also provide a prediction of the effective moment of inertia of CO in the He nano-droplet regime, which has not been measured so far.