Exposing vanadium oxide nanoparticles on a Pd(111) surface to reducing conditions is shown to cause a spreading of the oxide over the metal until a reduced oxide phase covers the entire surface. Reoxidation reverses this process and oxide island structures and bare metal patches are reestablished. The physical origin of this wetting-dewetting process is revealed at the atomic level by in situ variable-temperature scanning tunneling microscopy and in terms of a surface oxide phase stability diagram, as calculated by density functional theory as a function of the chemical potential of oxygen and the vanadium concentration.