Experimental evidence suggests that Pd clusters on MgO, known to be good reaction catalysts, have face centered cubic (fcc) epitaxial structures. The structure of such clusters is the result of the interplay of Pd-Pd and Pd-substrate bonds, the former inclined to favor icosahedral (Ih) and decahedral (Dh)-like structures, the latter leading to place Pd atoms on top of oxygen sites, according to an epitaxial stacking. This paper shows the results of a basin-hopping global optimization procedure applied to free and MgO-supported Pd clusters in the size range 10 <= N <= 120. Pd-MgO interactions are modeled by an analytical function fitted to ab initio results, while Pd-Pd interactions are modeled by a semiempirical potential. Besides the tightbinding Rosato-Guillope-Legrand (RGL) potential, we have adopted a modified version of RGL that better reproduces the experimental surface energy of palladium, modifying the attractive part of Pd atoms potential energy. We have compared the two potential models, and as a result, the RGL potential favors clusters with epitaxial arrangements, so that cluster structures are epitaxial fcc in almost all the size ranges considered. On the contrary, the alternative potential model preserves some Ih-like characteristics typical of the free Pd clusters, and it suggests that a transition size from Ih-like to epitaxial structures can take place at about 100 atoms.