Nitric oxide (NO) is an important air pollutant. Its chemical conversion to ammonia (NH3) and water (H2O) molecules has recently attracted a lot of experimental attention. In this work, we have employed a periodic density functional theory method combined with a slab model to study the catalytic reaction of NO adsorbed on a hydroxylated rutile TiO2(110) surface. We have obtained two favorable NO adsorption structures: in the first one, the terminal N atom is bonded with a Ti-Sc, surface atom (NadO); in the second one, both the N and O atoms are bonded with two nearby Ti-Sc surface atoms (NadOad). Interestingly, NadOad becomes more stable than NadO with the increasing coverage of hydroxyl groups, i.e., more than three hydroxyl groups in our slab model, which demonstrates that hydroxyls can seriously influence surface electronic structures and, thus, surface catalysis. Mechanistically, we have found that the N-O bond should be weakened prior to its dissociation. In the NadO adsorption structure, this weakening is achieved through a hydrogen atom transfer to the N atom of the NO molecule; in the NadOad adsorption structure, this N-O bond is already activated upon adsorption,on the surface. After the N-O bond is broken, a series of hydrogen atom transfers to either the N or O atom take place, which eventually produces the final products. Our present computational results provide important mechanistic insights into NO removal from TiO2 surfaces.