By means of scanning tunneling microscopy and density functional theory calculations, we studied the water formation reaction on the Rh(110) surface when exposing the (2 × 1)p2mg-O structure to molecular hydrogen, characterizing each of the structures that form on the surface during the reaction. First the reaction propagates on the surface as a wave front, removing half of the initial oxygen atoms. The remaining 0.5 monolayers of O atoms rearrange in pairs, forming a c(2 × 4) structure. Second, as the reaction proceeds, areas of an intermediate structure with c(2 × 2) symmetry appear and grow at the expense of the c(2 × 4) phase, involving all the oxygen atoms present on the surface. Afterward, the c(2 × 2) islands shrink, indicating that complete hydrogenation occurs at their edges, leaving behind a clean rhodium substrate. Two possible models for the c(2 × 2) structure, where not only the arrangement but also the chemical identity is different, are given.