The oxidation of Pd(111) leads to an incommensurate surface oxide, which was studied by the use of scanning tunneling microscopy, surface x-ray diffraction, high resolution core level spectroscopy, and density functional calculations. A combination of these methods reveals a two-dimensional structure having no resemblance to bulk oxides of Pd. Our study also demonstrates how the atomic arrangement of a nontrivial incommensurate surface can be solved by molecular dynamics in a case where experimental techniques alone give no solution.