We show that coverage fluctuations on catalyst particles can drastically alter their macroscopic catalytic behavior. Scrutinizing the occurrence of kinetic bistabilities, it is demonstrated by molecular beam experiments on model catalysts that macroscopically observable bistabilities vanish completely with decreasing particle size, as previously predicted by theory. The effect is attributed to fluctuation-induced transitions between two kinetic reaction regimes, with a transition rate controlled by both particle size and surface defects. These results suggest that fluctuation-induced effects represent a general phenomenon affecting the reaction kinetics on nanostructured surfaces.