Platinum and palladium are metals of fundamental importance in heterogeneous catalysis, but only in the last years light has been shed on the oxide structures that form on these metals in an oxygen rich environment. In this talk recent results on platinum and palladium oxides are presented, obtained by density functional theory and ab-initio thermodynamics. Investigated phases include ultrathin oxide films at surfaces, partly oxidized nanoparticles and platinum oxide nanotubes.