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 overlayer. The shape of oxygen-covered Pd and Pt nanoparticles is compared in this study.