The structural, electronic and magnetic properties of Pdn (n = 6, 13) clusters supported on (110) surface of TiO2 rutile have been studied using ab initio ultrasoft pseudopotential calculations within generalized gradient approximation. The magnetic moments and atomic structures of these clusters have only small changes when soft landed on the oxide surface. The magnetic moments of Pd13 cluster on TiO2 (110) surface is reduced to 6 $\mu$B as compared to 8 $\mu$B for free cluster. Our calculations also show that the adsorption energy differences between various orientations of Pd13 cluster on the surface of the slab are small. Therefore, nearly spherical clusters such as Pd13 can roll and have high mobility. The calculated adsorption energies of Pd 6 and Pd13 on the (110) surface of TiO2 slab are approximately 2.2 and 2.4 eV, respectively. {\textcopyright} World Scientific Publishing Company.