The effect of cluster size, oxidation state, and the support upon the structures and energetics of subnanometer palladium nanoparticles is investigated within a density functional framework. Gas phase global minima of Pd<sub>4</sub> and Pd<sub>10</sub> along with their suboxide counterparts are determined using a genetic algorithm and deposited upon MgO (001) and a high-index alumina surface. It is observed that there is an oxidation-dependent transition in the smaller clusters from three-dimensional to two-dimensional structures both in the gas phase and when supported by a surface. MgO strongly promotes a change from tetrahedral- and icosahedral-based structures toward cubic forms, while alumina induces significant distortion of the clust...