We performed a combined experimental and theoretical study of surface stress and structure of the adsorption of oxygen on Ir(001). We find that up to an oxygen coverage of half a monolayer oxygen adsorbs in bridge sites, whereas at larger coverage between 0.5 and 0.75 adsorption occurs in both bridge and hollow sites. A compressive surface stress change of -2.2 N/m is measured, and substantial lattice relaxations are identified by surface x-ray diffraction. Density-functional theory calculations reveal that anisotropic O-induced surface stress is a key factor for the sequential occupation of the adsorption sites.