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 and Pd 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 cluster and the breaking of Pd-Pd bonds. Increased oxygenation contributes cooperatively to these effects, causing disruption of the Pd-Pd bond network, favoring the incorporation of oxygen into the cluster structure, further complicating unambiguous structure prediction.