A detailed surface reaction mechanism for oxidation of CO on polycrystalline Pt surfaces, capable of predicting various available experimental features, has been developed using a multistep methodology. First, thermodynamically consistent, coverage-dependent activation energies and heats of reactions were derived from the application of the unity bond index-quadratic exponential potential formulation. Next, initial estimates of pre-exponentials were obtained from transition state theory or available experiments. Important feature identification analysis was performed to determine key reaction parameters for each experiment. Model responses were then parameterized in terms of these important parameters by simple polynomials and factorial design techniques and subsequently used in simultaneous optimization through simulated annealing against different sets of literature and new experimental data from our laboratory. Model validation with independent experiments shows that the proposed surface reaction mechanism performs very well. The potential of our approach for developing surface reaction mechanisms for catalytic combustion of more complex fuels is also discussed.