The development of room-temperature equilibrium surface structures of Pd(110) has been investigated with scanning tunneIing microscopy (STM). Mesoscopic ordering of islands has been found on oxygen-induced reconstructed and also on subsequently titrated Pd(110). Namely, the Pd(110)-c(2 x 4)-O, Pd(110)-(1 x 2) and Pd(110)-(1 x 3) surfaces form two-dimensional mesostructures. A similar class of ordering seems to be absent on clean Pd(110)-(1 x 1). The oxygen-free (1 x 2) and (1 x 3) reconstructions consist on an atomic scale of single and double rows, respectively, of Pd atoms, separated by single missing rows. The c(2 x 4)-O superstructure is created upon high-temperature oxygen exposure. The surface reconstruction can be explained by single added rows of Pd atoms with two oxygen atoms per every other Pd atom being adsorbed in the upper-layer hcp (111) sites. A sponge-like Pd surface is obtained after high oxygen dosing, which probably indicates the beginning of subsurface oxygen formation.