The interaction of small Pd-n clusters (n = 3, 4) with the relaxed Al-terminated alpha-Al2O3(0001) surface has been investigated using embedded cluster and periodic slab models within a first principles density functional approach. From the present study, it is concluded that the structure of supported Pd-3 is largely distorted from the gas-phase equilibrium geometry whereas the structure of supported Pd-4 is less distorted and reminiscent of the most stable gas-phase isomer. Consequently, the adhesion energy of Pd-3 on the relaxed alpha-Al2O3(0001) surface is smaller than that of Pd-4. The presence of Pd atoms induces a rather large reorganization of the atomic structure of the surface. The results obtained for the different structures of supported Pd-4 suggest that there is a competition between 2D and 3D growth of the supported crystallites. Also, in contrast to the results obtained for Pd adsorption on other oxide surfaces, there are no preferred adsorption sites for Pd deposited on the corundum surface.