A novel type of temporal and spatial self-organization in a heterogeneous catalytic reaction is described for the first time. Using in situ x-ray photoelectron spectroscopy, gas chromatography, and mass spectrometry, we show that, under certain conditions, self-sustained reaction-rate oscillations arise in the oxidation of propane over Ni foil because of reversible bulk oxidation of Ni to NiO, which can be observed even with the naked eye as chemical waves propagating over the catalyst surface.