Results of dynamic Monte Carlo simulations of a model for CO oxidation on a reconstructing Pt(100) surface are presented. A comparison is made between simulations that explicitly include surface diffusion of adsorbed CO and simulations without diffusion. Oscillatory behavior as well as spatio-temporal pattern formation are studied as a function of system size, In the absence of diffusion the amplitude of kinetic oscillations decreases with grid size and oscillations are not stable. Spatio-temporal patterns appear, as expected for an excitable medium. Such patterns become stabilized by structural substrate defects. The length scale of the patterns is in the order of 10-100 nm, the temporal period of the oscillations is around 200 seconds. Inclusion of diffusion stabilizes and synchronizes oscillations. Spatio-temporal features now appear with larger spatial dimensions.