The catalytic removal of heteroatoms from renewable bio-oils in supercritical water (SCW) is challenged by the lack of sufficiently stable catalysts. We identified a library of catalytic materials that are thermodynamically stable under hydrodenitrogenation (HDN) conditions, based on oxygen fugacity-pH diagrams. From among these, we selected a Pt/TiO2 catalyst for HDN of propylamine in SCW at 380-500 degrees C and 22-38 MPa. Flow experiments with aqueous feeds of formic acid, ammonia, and propylamine were designed to isolate interactions between the catalyst, the SCW solution, and the reactants and products. The Pt/TiO2 catalyst was highly active and experienced negligible dissolution at 500 degrees C, 2% Pt loss at 380 degrees C, and no changes in oxidation state. Overall, the experimentally observed hydrothermal stabilities of the catalyst agreed with the thermodynamic stabilities predicted. The results and methodology applied in this work may be useful to identify and design catalysts for bio-oil upgrading in hydrothermal media.