The catalytic oxidation of CO and CH4 can be strongly influenced by the structures of oxide phases that form on metallic catalysts during reaction. Here, we show that an epitaxial PdO(100) structure forms at temperatures above 600 K during the oxidation of Pd(100) by gaseous O atoms as well as exposure to O2-rich mixtures at millibar partial pressures. The oxidation of Pd(100) by gaseous O atoms preferentially generates an epitaxial, multilayer PdO(101) structure at 500 K, but initiating Pd(100) oxidation above 600 K causes an epitaxial PdO(100) structure to grow concurrently with PdO(101) and produces a thicker and rougher oxide. We present evidence that this change in the oxidation behavior is caused by a temperature-induced change in the stability of small PdO domains that initiate oxidation. Our discovery of the epitaxial PdO(100) structure may be significant for developing relationships among oxide structure, catalytic activity, and reaction conditions for applications of oxidation catalysis.