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 x 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 x 4) structure. Second, as the reaction proceeds, areas of an intermediate structure with c(2 x 2) symmetry appear and grow at the expense of the c(2 x 4) phase, involving all the oxygen atoms present on the surface. Afterward, the c(2 x 2) islands shrink, indicating that complete hydrogenation occurs at their edges, leaving behind a clean rhodium substrate. Two possible models for the c(2 x 2) structure, where not only the arrangement but also the chemical identity is different, are given. The first one is a mixed H + O structure, while the second one resembles the half-dissociated water layer already proposed on other metal surfaces. In both models, the high local oxygen coverage is achieved by the formation of a hexagonal network of hydrogen bonds.