The morphology, structure, and reactivity of vanadium oxide-decorated Pd(111) surfaces, which have been subjected to oxidation and reduction treatments, have been investigated by scanning tunneling microscopy (STM), high-resolution electron energy loss spectroscopy (HREELS), and high-resolution X-ray photoelectron spectroscopy (HR-XPS) with synchrotron radiation combined with ab initio density functional theory (DFT) calculations. Two major oxide phases form on the Pd(111) surface following the oxidation (V5O14) and reduction (s-V2O3) treatments; their structures have been revealed with the help of the DFT calculations. The reactive sites of both oxidized and reduced vanadium oxide/Pd(111) surfaces have been studied using the adsorption of CO as a test molecule for probing the free Pd sites. The adsorbate (C 1s) and substrate (Pd 3d) core level XPS data show that on the reduced, s-V2O3-decorated Pd(111) surfaces, CO occupies the same adsorption sites as on the clean Pd(111). In contrast, a new type of CO adsorption site is found on the oxidized, V5O14-covered Pd(111) surfaces that is associated with the adsorption of CO within the open (4 x 4) oxide lattice. The latter contains holes with six free Pd atoms per unit cell, which may be considered as a particular kind of an "adsorption pocket".