We used temperature-programmed reaction spectroscopy (TPRS) to study the reactivity of propane on oxidized Pd(111) surfaces that were prepared by partially oxidizing Pd(111) as well as partially reducing a PdO(101) thin film in ultrahigh vacuum. These experiments were motivated in large part by recent observations of multiple phases co-existing during the autocatalytic thermal decomposition of a PdO(101) thin film, and the possibility that such phases exhibit distinct reactive properties. We find that the surface reactivity toward propane oxidation increases monotonically with increasing surface oxygen concentration, but that the reactivity exhibits a slight hysteresis as a function of oxygen coverage for surfaces prepared by Pd(111) oxidation vs. PdO(101) reduction. Based on the observation that propane desorbs in distinct features from different Pd-oxide phases, we determined that the hysteresis in reactivity arises from differences in the amount of PdO(101) domains present on partially oxidized vs. reduced surfaces and present evidence that propane reacts exclusively on PdO(101) domains even when a mixture of surface phases is present. We show that deconvolution of the propane desorption traces also allows us to estimate the relative fractions of surface phases which develop during both oxide growth and reduction, and thus provides a means to quantify the phase evolution as a function of oxygen coverage. The analysis demonstrates that metallic domains as well as phases characteristic of monolayer oxides, so-called surface oxides, develop during the early stages of reduction of a multilayer PdO(101) film and appear to form on top of the multilayer oxide. This finding clarifies the nature of new structures that were observed in prior STM studies of PdO(101) film decomposition, and provides key insights for understanding the processes governing oxide decomposition.