Silica-supported Pd nanoclusters (Pdn/SiO2) are essential catalysts in methane oxidation for pollution abatement. These catalysts operate at high temperature for long periods exposed to the exhaust gases of combustion engines. For catalyst design to ensure the required longevity, insight into the interaction between nanoclusters and the SiO2 surface is essential. Accordingly, there is a need for well-defined, computationally inexpensive, quantum mechanical models of these structures from which cluster support interactions can be understood. In this work, we have found that a strong adsorption site for a single Pd1 atom on the hydroxylated α-SiO2(101) surface can be formed when Pd adsorption is accompanied by the elimination of water. We show that this becomes a thermodynamically favourable process at the temperatures commonly used for calcination following catalyst synthesis using wet impregnation. Using this initial anchor point Pdn and Pdn(xO) nanoclusters are systematically constructed guided by the Mulliken charges of atoms at each stage. We then investigate the surface interactions of these Pdn and Pdn(xO) nanoclusters by considering the gas phase references of the same clusters. Our calculations show stability varies according to cluster size. Oxidation of the clusters leads to a weakening of cluster-surface interaction.