We show that advances in two fields of computational chemistry, Dynamic Monte Carlo simulations and Density-Functional Theory calculations, are now making it possible to do ab-initio kinetics of realistic surface reactions. We present results of simulations of Temperature-Programmed Desorption experiments of NO reduction to N2 and O2 on the Rh(111) surface. Kinetic parameters were obtained from Density- Functional Theory calculations with the Generalized Gradient Approximation, making this one of the first, and up till now the most complex, example of ab-initio kinetics in heterogeneous catalysis. Top, hcp, and fcc sites are all involved and also lateral interactions are necessary to understand the kinetics of this system.