To investigate the effect of adsorbates on structural transitions in small palladium aggregates, we have performed molecular dynamics simulations of cluster “melting” in presence of atomic hydrogen. Intriguing questions are how the exposure to hydrogen modifies the metal-metal interaction, and whether hydrogen could lower the onset of melting. Various structural and caloric methods were used to capture signatures of melting. We present results for the bare icosahedral Pd55 cluster and also Pd55 exposed to different amounts of hydrogen. Our results indicate that the melting transition is significantly lowered as hydrogen adsorbs on the cluster, and that the decrease in melting temperature depends sensitively on the hydrogen loading.