Using a first-principles parameterized lattice-gas Hamiltonian we study the adsorbate ordering behavior at atomic steps of a Pd(100) surface exposed to an oxygen environment. We identify a wide range of gas-phase conditions comprising near atmospheric pressures and elevated temperatures around 900 K, in which the step is decorated by a characteristic O zigzag arrangement. For catalytic processes like the high-temperature combustion of methane that operate under these conditions our approach thus provides first insight into the structure and composition at a prominent defect on the working surface. (C) 2008 Elsevier B.V. All rights reserved.