Nanostructured RuOx/TiO2(110) catalysts have a remarkable catalytic activity for CO oxidation at temperatures in the range of 350-375 K. On the other hand, the RuO2(110) surface has no activity. The state-of-the-art DFT calculations indicate that the main reasons for such an impressive improvement in the catalytic activity are: (i) a decrease of the diffusion barrier of adsorbed O atoms by around 40%, from 1.07 eV in RuO2(110) to 0.66 eV in RuOx/TiO2(110), which explains the shift of the activity to lower temperatures and (ii) a lowering of the barrier by 20% for the association of adsorbed CO and O species to give CO2 (the main barrier for the CO oxidation reaction) passing from around 0.7 eV in RuO2(110) to 0.55 eV in RuOx/TiO2(110). We show that the catalytic properties of ruthenia are strongly modified when supported as nanostructures on titania, attaining higher activity at temperatures 100 K lower than that needed for pure ruthenia. As in other systems consisting of ceria nanostructures supported on titania, nanostructured ruthenia shows strongly modified properties compared to the pure oxide, consolidating the fact that the nanostructuring of oxides is a main way to attain higher catalytic activity at lower temperatures.