We present a density-functional theory trend study addressing the incorporation of oxygen into the basal plane of the late 4d transition metals (TMs) from Ru to Ag. Occupation of subsurface sites is always connected with a significant distortion of the host lattice, rendering it initially less favorable than on-surface chemisorption. Penetration starts only after a critical coverage theta(c), which is lower for the softer metals towards the right of the TM series. The computed theta(c) are found to be very similar to those above which the bulk oxide phase becomes thermodynamically more stable, thus suggesting that the initial incorporation of O actuates the formation of a surface oxide on TM surfaces.