Temperature-programmed reaction spectroscopy has been used to study the surface reaction between CO and O-atoms on Rh(100) and Rh(111) at a range of different adsorbate coverages. Comparison of the reaction on both surfaces in the low coverage regime, where the kinetics can be described by a straightforward Langmuir-Hinshelwood mechanism reveals that the CO oxidation is structure sensitive, with the rate constant being an order of magnitude higher on the Rh(100) than on the Rh(111) surface. As a consequence, the selectivity of the CO+O reaction to CO2 is about 100% on Rh(100), whereas on Rh(111) the oxidation reaction competes with CO desorption. At low CO coverage, CO oxidation is an elementary step on Rh(100) for a broad range of oxygen coverages. We report kinetic parameters E-a=103 +/- 5 kJ/mol and nu=10(12.7 +/- 0.7) for theta(O)=theta(CO)--> 0 on Rh(100). The activation energy for CO oxidation on Rh(100) decreases continuously with increasing O-coverage. At low coverage (theta(O)< 0.25 ML) we attribute this to destabilization of CO, leading to an increase in the CO2 formation rate. At higher coverage (theta(O)> 0.25 ML) O-atoms become destabilized as well, as lateral interactions between O-atoms come into play at these coverages. The interactions result in a greatly enhanced rate of reaction at higher coverages.