A mesoscopic stochastic model of the catalytic reaction 2CO+O-2-->2CO(2) on the surface of a metal particle is considered. The model is a Markovian chain of elementary reaction steps, which mimics the catalytic oxidation of CO on a nm-sized Pd particle. The model takes into account the effect of the particle size on the reaction rate and the role of temporal fluctuations of the concentrations of the reactants. The main goal of the paper is the comparison of the dynamics produced by the stochastic model and the deterministic model obtained via averaging of the master equation, while the catalyst particle size is reduced. Intrinsic fluctuations during the reaction are shown to change the reaction kinetics drastically for small metal particles with only several hundreds of surface atoms.