Using density functional theory (DFT) and thermodynamic considerations we study the shape and stability of Pd nanoparticles in oxygen-lean and oxygen- rich atmospheres. We find that at very high oxygen coverage cubes exposing (100) faces will form, which are stabilized due to the formation of a Image o/√(5) x √(5)R27° overlayer. The shape of oxygen-covered Pd and Pt nanoparticles is compared in this study.