We present Monte Carlo simulations of phase separation during kinetic oscillations in catalytic reactions accompanied by adsorbate-induced surface restructuring. As an example, we analyze the NO-H-2 reaction on Pt(100). The lattice-gas model employed to describe surface restructuring and the reaction steps takes into account substrate-substrate, substrate-adsorbate and adsorbate-adsorbate lateral interactions. Using a reduced generic mechanism of the reaction, we show the type of spatio-temporal patterns which might be observed on the nm scale.