By use of density-functional theory we analyze the on-surface adsorption of oxygen on Pd(111) for coverages up to 1 monolayer and compare the results with corresponding data for the other late 4d transition metals, namely, Ru, Rh, and Ag. Besides the known effect of the continued d-band filling on the oxygen-metal bond strength, we also discern trends in the adsorption geometries, work functions, and electron density of states. The repulsive lateral interactions in the overlayer give rise to a pronounced reduction of the adsorption energy at higher on-surface coverages. In fact, for oxygen coverages theta > 0.5 monolayers, the thermodynamic equilibrium phase of O/Pd(111) is known to be a surface oxide. The calculations reported in this paper show that on-surface adlayers at such higher coverages, that may exist as metastable phases, still possess qualitatively the same surface chemical bond as that which is found at low coverages. The dependence of the surface relaxation on oxygen coverage exhibits some unexpected behavior.