Anisotropic adsorbate-induced biaxial surface stress is measured for the adsorption of sub-monolayers of Fe and O on W(110). Half a monolayer of Fe induces compressive stress of -2 N/m along W[001] and tensile stress of +1 Nlm along W[(1) over bar 10], whereas a (2 x 1)-O structure induces compressive stress of -1.1 N/m along W[(1) over bar 10], and causes only a minute stress of -0.1 N/m along W[001]. The O-induced surface stress is ascribed to a release of the anisotropic surface stress of the clean W crystal, whereas for Fe coverages, the surface stress of the Fe-W composite determines the measured stress.