We present calculated adsorption energies of oxygen on gold and platinum clusters with up to 923 atoms (3 nm diameter) using density functional theory. We find that surface tension of the clusters induces a compression, which weakens the bonding of adsorbates compared with the bonding on extended surfaces. The effect is largest for close-packed surfaces and almost nonexistent on the more reactive steps and edges. The effect is largest at low coverage and decreases, even changing sign, at higher coverages where the strain changes from compressive to tensile. Quantum size effects also influence adsorption energies but only below a critical size of 1.5 nm for platinum and 2.5 nm for gold. We develop a model to describe the strain-induced size effects on adsorption energies, which is able to describe the influence of surface structure, adsorbate, metal, and coverage.