Catalytic water formation from adsorbed H and O adatoms is a fundamental reaction step in a variety of technologically important reactions involving organic molecules. In particular, the water-formation rate determines the selectivity of the catalytic partial oxidation of methane to syngas. In this report we present a theoretical investigation of the potential-energy diagram for water formation from adsorbed O and H species on Rh(111) and Pt(111) surfaces. The study is based on accurate first-principles calculations applying density-functional theory. Our results are compared to the potential-energy diagram for this reaction inferred from experimental data by Hickman and Schmidt [AIChE. J. 39, 1164 (1993)]. The calculations essentially reproduce the scheme of Hickman and Schmidt for water formation on Rh(111) with the important difference that the OH molecule is significantly more stable than assumed by Hickman and Schmidt. On Pt(111) surfaces, however, the calculations predict a barrier to OH formation very similar to that found on Rh(111). In particular, the calculated barrier to OH formation of about 20 kcal/mol seems to contradict the small 2.5 kcal/mol barrier assumed in the Hickman-Schmidt scheme and the observed large rate of water formation on Pt. A possible explanation for the apparent discrepancy between the large calculated barrier for OH formation on Pt and the experimentally observed rapid formation of water even at low temperatures is that the active sites for water formation on Pt are at "defect" sites and not on the ideally flat terraces. A similar conclusion has been reached by Verheij and co-workers [Surf. Sci. 371, 100 (1997); Chem. Phys. Lett. 174, 449 (1990); Surf. Sci. 272, 276 (1991)], who did detailed experimental work on water formation on Pt surfaces. Analyzing our results, we develop an explicit picture of the interaction processes governing the formation of OH groups. This picture rationalizes the calculated weak dependence of OH formation on substrate material. An important conclusion from this work is that "good" catalysts for the partial oxidation of hydrocarbons should resist defect formation at their surfaces.