A model catalyst system, palladium on tungsten oxide, has been examined by temperature-programmed desorption and photoemission spectroscopy. The samples were prepared by evaporation of palladium onto an oxidized tungsten foil under ultrahigh vacuum conditions. Mostly three-dimensional (3-D) palladium (Pd) clusters were found to be present on oxidized tungsten (WOx) surfaces at room temperature. Upon annealing to 670 K, the palladium clusters are redispersed and decorated by the WOx surface layer. The nature of the WOx phase on top of the palladium clusters is dependent on the mode of oxidation of the tungsten foil prior to palladium deposition. Mainly W(2+) species decorate palladium deposits on tungsten oxidized at room temperature, while mainly W(4+) species are on top of palladium deposits on the surface oxidized at 1300 K. The appearance of a Pd(n+)-O-W(4+) mixed oxide phase with n < 2 was observed on the oxidized tungsten surface. The substantial reduction (relative to nonannealed samples) of molecular CO coverage induced by annealing is discussed in terms of the changes in chemical composition and morphology of the outermost surface.