Infrared laser spectroscopy was used to probe the unique rotational dynamics of the HCN-M (M = Na, K, Rb, Cs) complexes formed on the surface of helium droplets. The nu(1) CH stretch ro-vibrational spectra were measured revealing what appears to be the P and R contours of a nearly rigid linear rotor. To simulate the linear molecule spectra, given a rotational temperature of 0.37 K, effective moments of inertia, I-B, were required to be 10(4)-10(5) amu center dot angstrom(2) larger than the ab initio predicted values. The large moments of inertia were found to be strongly dependent on both the mass of the complex and the size of the helium droplet, consistent with a model where the dopant is located in a dimple site on the surface of the droplet. In this model, the moment of inertia is representative of the rotational motion of the dopant on the surface about an inertial axis through the center of the droplet.